Speichereffiziente Implementierungen partieller Singular Value Decompositions (SVD)

10

Zur Modellreduktion möchte ich die linken Singularvektoren berechnen, die den - sagen wir 20 - größten Singularwerten einer Matrix , wobei und . Leider wird meine Matrix ohne Struktur dicht sein. $A \in \mathbb R^{N,k}$ $N\approx 10^6$ $k\approx 10^3$ $A$

Wenn ich nur die svdRoutine aus dem numpy.linalgModul in Python für eine Zufallsmatrix dieser Größe aufrufe, tritt ein Speicherfehler auf. Dies ist auf die Zuordnung von für die Zerlegung . $V\in \mathbb R^{N,N}$ $A = VSU$

Gibt es Algorithmen, die diese Gefahr vermeiden? Zum Beispiel durch Einrichten nur der Singularvektoren, die mit Singularwerten ungleich Null assoziiert sind.

Ich bin bereit, mit Rechenzeit und Genauigkeit zu handeln.

linear-algebra python reference-request numpy svd Jan.
quelle

1

Interessant, es scheint, dass Numpy nicht weiß, wie man eine dünne SVD macht ...

JM

Danke für den Tipp. In der Tat hat numpy.linalg.svd die Option full_matrices, die auf False gesetzt wird, damit nur die Teile ungleich Null berechnet werden. Gibt es dennoch eine Möglichkeit, die Berechnung noch weiter zu reduzieren?

Januar

3

Das numpyBackend verwendet fortran Code, die LAPACKE_dgesvdRoutine für Standard-DVDs. Normalerweise ist Ihre Matrix jedoch C_CONTIGOUS(überprüfen Sie mit matrix.flags). Daher werden die Daten für die Fortran-Ausrichtung kopiert. Zusätzlich wird beim Ausführen der Lapack-Routine dgesvd eine weitere Kopie Ihrer Matrix benötigt (oder zumindest der Speicher dafür). Sie können eine Kopie entfernen, wenn Sie sicherstellen, dass die Speicherausrichtung von Anfang an im fortran-Stil erfolgt.

Bort

6

Wenn Sie nur einige einzelne Werte / Vektoren möchten, sollte ARPACK den Trick ausführen . Die SVD-Dokumente sind nicht besonders gut und diese Distribution ist aktueller.

BEARBEITEN: Wenn Sie dies in Python tun möchten, verfügt SciPy über einen Wrapper . Da Ihre Matrix dicht ist, können Sie das BSR-Format ( Block Sparse Row ) ausprobieren .

Max Hutchinson
quelle

Ich werde einen Blick darauf werfen, wie sich ARPACK in Python integriert ...

Januar

1

Sieht aus wie scipy hat Wrapper. Ich werde sie hinzufügen, um Körper zu beantworten.

Max Hutchinson

2

Schauen Sie sich sklearn.decomposition.TruncatedSVD in scikit-learn 0.14 -rc an.
(Ich glaube, dass die Leute, die Scikit lernen, stackoverflow.com/questions/tagged/scikit-learn folgen , also würde ich dort detaillierte Fragen stellen.)

(Wie viel Speicher haben Sie? 10 verdoppelt ist bereits 8G.) $^{6+3}$

denis
quelle

Danke für deine Antwort. Inzwischen mache ich mich gut mit den Scipy-Routinen. Außerdem bin ich noch nicht bis gegangen, aber auf ungefähr die Hälfte davon, was für meinen Laptop noch machbar ist. Bei Bedarf kann ich einen Arbeitscomputer mit 32 GB RAM verwenden.

10^{6} \times 10^{3}

$10^6 \times 10^3$

Jan

2

Vielleicht kannst du das versuchen.

https://github.com/jakevdp/pypropack

Dies ist ein Python-Wrapper für das PROPACK-Paket, der effiziente partielle Singularwertzerlegungen großer, dünn besetzter Matrizen und linearer Operatoren implementiert.

Masse Zhou
quelle

2

Intel MKL implementiert den neuen Jacobi-SVD-Algorithmus. Hier sind die Implementierungsdetails: http://www.netlib.org/lapack/lawnspdf/lawn169.pdf http://www.fernuni-hagen.de/MATHPHYS/veselic/downloads/j02.pdf

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

Die Arbeitsgröße ist natürlich einstellbar. Sie können C-Funktionen von Python aus problemlos mit Cython, SWIG oder einem anderen Wrapping-Mechanismus aufrufen.

Tolga Birdal
quelle

Speichereffiziente Implementierungen partieller Singular Value Decompositions (SVD)

Antworten: