Wie berechnet man die SVD einer riesigen, dünn besetzten Matrix?

26

Was ist der beste Weg, um die Singulärwertzerlegung (SVD) einer sehr großen positiven Matrix (65M x 3,4M) zu berechnen, bei der die Daten extrem dünn sind?

Weniger als 0,1% der Matrix ist nicht Null. Ich brauche einen Weg, der:

  • passt in den Speicher (ich weiß, dass Online-Methoden existieren)
  • wird in einer angemessenen Zeit berechnet: 3,4 Tage
  • wird genau genug sein, aber Genauigkeit ist nicht mein Hauptanliegen und ich möchte in der Lage sein zu kontrollieren, wie viel Ressourcen ich in sie stecke.

Es wäre toll, eine Haskell-, Python-, C # - usw. Bibliothek zu haben, die diese implementiert. Ich benutze weder Mathlab noch R, kann aber bei Bedarf mit R gehen.

svd numerics Sonia
quelle
3
Wie viel Gedächtnis hast du? 0,1% von 65M * 3,4M sind immer noch 221e9 Werte ungleich Null. Wenn Sie 4 Bytes pro Wert verwenden, sind das immer noch mehr als 55 GB, vorausgesetzt, es entsteht kein Overhead, sodass das Problem durch die geringe Speicherkapazität immer noch nicht behoben wird. Müssen Sie den gesamten Satz auf einmal in den Speicher laden?
Bitweise
Ich hätte präziser sein sollen. Nicht mehr als 250-500 MB mit 32-Bit-Ganzzahl. Wahrscheinlich viel weniger, aber die Dimensionalität ist das Problem, wie ich es verstehe. Ich habe eine 16GB Maschine.
Sonia
Wie wäre es damit? quora.com/…
Bitwise
Diese Webseite verweist auf eine Python-Bibliothek, die "einen schnellen, inkrementellen SVD-Algorithmus mit geringem Arbeitsspeicher und großer Matrix"
implementiert
Siehe auch stats.stackexchange.com/questions/2806 .
Amöbe sagt Reinstate Monica

Antworten:

21

Wenn es in den Speicher passt, konstruieren Sie mit dem Matrix-Paket eine dünne Matrix in R und versuchen Sie es mit irlba für die SVD. Sie können angeben, wie viele singuläre Vektoren im Ergebnis enthalten sein sollen. Auf diese Weise können Sie die Berechnung einschränken.

Das ist eine ziemlich große Matrix, aber ich habe mit dieser Methode in der Vergangenheit sehr gute Ergebnisse erzielt. irlbaist ziemlich auf dem neuesten Stand der Technik. Es verwendet den implizit neu gestarteten Bidiagonalisierungsalgorithmus von Lanczos .

Es kann den Netflix-Preisdatensatz (480.189 Zeilen x 17.770 Spalten, 100.480.507 Einträge ungleich Null) in Millisekunden durchkauen. Ihr Dataset ist ca. 200.000-mal größer als das Netflix-Dataset, daher dauert es erheblich länger. Es ist zu erwarten, dass die Berechnung in ein paar Tagen durchgeführt werden kann.

Zach
quelle
Die Datenmatrix passt in den Speicher. Wird irlba die Zerlegung auch auf speichereffiziente Weise handhaben?
Sonia
@Sonia: irlba ist sehr speichereffizient: Es berechnet eine ungefähre Lösung, Sie können die Anzahl der singulären Vektoren begrenzen und es wurde für die Arbeit mit spärlichen Matrizen entwickelt. Soweit ich weiß, ist es so schnell wie möglich, partielle SVDs zu berechnen.
Zach
@Sonia: Viel Glück!
Zach
Hab es ausprobiert ... Ich werde ein Dreieckblockformular berechnen, bevor ich es ausführe.
Sonia
@Sonia hast du es als spärlich gespeichert Matrix? Versuchen Sie, die Anzahl der von Ihnen berechneten Singularwerte zu begrenzen. Schauen Sie sich vielleicht nur die Top 10 an.
Zach