Implémentations efficaces en mémoire des décompositions partielles de valeurs singulières (SVD)

10

Pour la réduction du modèle, je veux calculer les vecteurs singuliers de gauche associés aux - disons 20 - plus grandes valeurs singulières d'une matrice , où N 10 6 et k 10 3 . Malheureusement, ma matrice A sera dense sans aucune structure.ARN,kN106k103A

Si j'appelle simplement la svdroutine du numpy.linalgmodule en Python pour une matrice aléatoire de cette taille, je rencontre une erreur de mémoire. Cela est dû à la répartition du pour la décomposition A = V S U .VRN,NA=VSU

Existe-t-il des algorithmes qui évitent cet écueil? Par exemple, en définissant uniquement les vecteurs singuliers associés à des valeurs singulières non nulles.

Je suis prêt à échanger du temps de calcul et de la précision.

Jan
la source
1
Intéressant, il semble que Numpy ne sait pas comment faire un SVD mince ...
JM
Merci pour l'astuce. En effet, numpy.linalg.svd a l'option full_matricesqui peut être définie sur False afin que seules les parties «non nulles» soient calculées. Néanmoins, existe-t-il un moyen de réduire encore plus le calcul?
Jan
3
Le numpybackend utilise le code fortran, la LAPACKE_dgesvdroutine pour svd standard. Cependant, votre matrice est généralement C_CONTIGOUS(vérifiez avec matrix.flags). Par conséquent, il copie les données pour l'alignement fortran. De plus, lors de l'exécution de la routine lapack dgesvd, une autre copie de votre matrice est nécessaire (ou au moins la mémoire correspondante). Vous pouvez vous débarrasser d'une copie si vous vous assurez que l'alignement de la mémoire est de style fortran dès le début.
Bort

Réponses:

6

Si vous ne voulez que quelques valeurs / vecteurs singuliers, ARPACK devrait faire l'affaire. Les documents SVD ne sont pas géniaux, et cette distribution est plus à jour.

EDIT: Si vous voulez faire cela en python, SciPy a un wrapper . Comme votre matrice est dense, vous pouvez essayer le format BSR ( Block Sparse Row ).

Max Hutchinson
la source
Je vais voir comment ARPACK s'intègre avec python ...
Jan
1
On dirait que scipy a des emballages. Je vais les ajouter pour répondre au corps.
Max Hutchinson
2

Vous pouvez peut-être essayer cela.

https://github.com/jakevdp/pypropack

Il s'agit d'un wrapper Python pour le package PROPACK, qui implémente des décompositions efficaces de valeurs singulières partielles de grandes matrices creuses et d'opérateurs linéaires.

Mass Zhou
la source
2

Intel MKL implémente le nouvel algorithme Jacobi-SVD. Voici les détails d'implémentation: http://www.netlib.org/lapack/lawnspdf/lawn169.pdf http://www.fernuni-hagen.de/MATHPHYS/veselic/downloads/j02.pdf

Et la routine LAPACK: http://software.intel.com/sites/products/documentation/hpc/mkl/mklman/GUID-732F9EE1-BCEC-4D9B-9B93-AF5499B21140.htm#DRMAC08-1

La taille du travail est bien sûr réglable. Vous pouvez facilement appeler des fonctions C à partir de Python en utilisant Cython, SWIG ou tout autre mécanisme d'encapsulation.

Tolga Birdal
la source