Welche schnellen Algorithmen gibt es für die Berechnung der abgeschnittenen SVD?

Möglicherweise nicht zum Thema hier, aber es gibt bereits mehrere ( eine , zwei ) verwandte Fragen.

Durch Stöbern in der Literatur (oder bei einer Google-Suche nach abgeschnittenen SVD-Algorithmen) tauchen viele Artikel auf , die abgeschnittene SVDs auf verschiedene Weise verwenden, und behaupten (frustrierend, oft ohne Angabe ), dass es schnelle Algorithmen gibt, um sie zu berechnen, aber niemand scheint darauf hinzudeuten, was diese Algorithmen sind.

Das einzige, was ich finden kann, ist ein einzelner randomisierter Algorithmus , der in der redSVD-Bibliothek verwendet wird .

Was ich sehen möchte, ist eine Reihe von exakten und ungenauen Algorithmen, die geeignet sind, die Funktionsweise der Systeme zu verstehen (aber nicht unbedingt, um sie tatsächlich zu implementieren!).

Hat jemand eine gute Referenz für so etwas?

algorithms svd numerics John Doucette
quelle

Wenn ich Daten gut speichern möchte, verwende ich einen B-Baum (oder RB-Baum) im Hash (denken Sie an RAM). Wenn ich einen B-Baum für die Daten hätte, dann könnte ich in O (log (n)) Zeit Quantile und dergleichen abtasten. Ich wette, dass bei großen Datenmengen eine solche Abtastung verwendet werden könnte, um in kurzer Zeit eine annehmbare spärliche Annäherung an die DVD-Matrizen zu berechnen. Sie können auch nach "Compressed Sensing" suchen, einem sehr statistischen Ansatz zur extremen Datenkomprimierung.

EngrStudent - Wiedereinsetzung von Monica am

Mit abgeschnittener SVD meinen Sie, dass Sie nur daran interessiert sind, mehrere führende singuläre Vektoren / Werte zu finden, im Gegensatz zu allen?

Amöbe sagt Reinstate Monica

@amoeba Ja, das ist die Idee.

John Doucette

Antworten:

Ganz allgemein gibt es zwei Ansätze zur Berechnung von Eigenwert- oder Singularwertzerlegungen. Ein Ansatz ist die Diagonalisierung der Matrix, die im Wesentlichen die gesamte Eigenwert- / Singulärwertzerlegung (das gesamte Eigenwertspektrum) zur gleichen Zeit ergibt. Sehen Sie hier eine Übersicht: Was sind effiziente Algorithmen zur Berechnung der Singulärwertzerlegung (SVD)? Die Alternative besteht darin, einen iterativen Algorithmus zu verwenden, der jeweils einen (oder mehrere) Eigenvektoren liefert. Iterationen können gestoppt werden, nachdem die gewünschte Anzahl von Eigenvektoren berechnet wurde.

Ich glaube nicht, dass es iterative Algorithmen speziell für SVD gibt. Dies liegt daran, dass man die SVD einer Matrix berechnen kann, indem man eine neue Zerlegung einer quadratischen symmetrischen -Matrix Deshalb , anstatt zu fragen , was Algorithmen berechnen abgeschnittener SVD, sollten Sie fragen, was iterative Algorithmen berechnen Eigendekomposition: $n\times m$ $\mathbf B$ $(n+m)\times(n+m)$

EIN = (\begin{array}{cc} 0 & B \\ B^{⊤} & 0 \end{array}) .

$\mathbf A=\left(\begin{array}{cc}0 & \mathbf B\\\mathbf B^\top & 0\end{array}\right).$

Algorithmus für abgeschnittene SVD \approx iterativer Algorithmus für die Eigendekomposition .

$\text{algorithm for truncated SVD} \approx \text{iterative algorithm for eigendecomposition}.$

Der einfachste iterative Algorithmus heißt Power-Iteration und ist in der Tat sehr einfach:

Initialisiere zufällig . $\mathbf x$
Aktualisiere . $\mathbf x \gets \mathbf A\mathbf x$
Normalisiere . $\mathbf x \gets \mathbf x / \|\mathbf x\|$
Gehe zu Schritt 2, sofern nicht konvergiert.

All die komplexeren Algorithmen basieren letztendlich auf der Idee der Power-Iteration, sind jedoch recht komplex. Notwendige Mathematik wird von Krylov-Subspaces angegeben . Die Algorithmen sind Arnoldi-Iteration (für quadratische unsymmetrische Matrizen), Lanczos-Iteration (für quadratische symmetrische Matrizen) und Variationen davon, wie z. B. "implizit neu gestartete Lanczos-Methode" und so weiter.

Dies können Sie zB in folgenden Lehrbüchern nachlesen:

Alle vernünftigen Programmiersprachen und Statistikpakete (Matlab, R, Python Numpy, wie Sie es nennen) verwenden die gleichen Fortran-Bibliotheken, um Eigen- / Singularwert-Zerlegungen durchzuführen. Dies sind LAPACK und ARPACK . ARPACK steht für ARnoldi PACKage und dreht sich alles um Arnoldi / Lanczos-Iterationen. In Matlab gibt es beispielsweise zwei Funktionen für SVD: Führt svdeine vollständige Zerlegung über LAPACK durch und svdsberechnet eine bestimmte Anzahl von Singularvektoren über ARPACK. Dies ist eigentlich nur ein Wrapper für einen eigsAufruf auf der "quadratischen" Matrix.

Aktualisieren

$\mathbf B$ $\mathbf A$ $\mathbf A$ $\mathbf B$ $\mathbf A$

Es gibt auch eine Fortran-Bibliothek für diese Methoden, die PROPACK heißt :

Das Softwarepaket PROPACK enthält eine Reihe von Funktionen zur Berechnung der Singulärwertzerlegung von großen und spärlichen oder strukturierten Matrizen. Die SVD-Routinen basieren auf dem Lanczos-Bidiagonalisierungsalgorithmus mit partieller Reorthogonalisierung (BPRO).

PROPACK scheint jedoch weitaus weniger Standard zu sein als ARPACK und wird von Haus aus in Standard-Programmiersprachen nicht unterstützt. Es wurde von Rasmus Larsen geschrieben, der 1998 eine große, 90 Seiten lange Lanczos-Bidiagonalisierung mit teilweiser Reorthogonalisierung mit scheinbar gutem Überblick veröffentlicht hat. Vielen Dank an @MichaelGrant über diesen Computational Science SE-Thread .

Unter den neueren Veröffentlichungen scheint Baglama & Reichel, 2005, Augmented, implizit neu gestartete Lanczos-Bidiagonalisierungsmethoden , die wahrscheinlich auf dem neuesten Stand der Technik sind , die populärste zu sein . Vielen Dank an @Dougal für diesen Link in den Kommentaren.

Update 2

In der Tat gibt es einen völlig anderen Ansatz, den Sie in dem von Ihnen zitierten Übersichtsartikel ausführlich beschrieben haben: Halko et al. 2009, Struktur mit Zufälligkeit finden: Probabilistische Algorithmen zur Konstruktion von approximativen Matrixzerlegungen . Ich weiß nicht genug darüber, um einen Kommentar abzugeben.

Amöbe sagt Reinstate Monica
quelle

Beachten Sie, dass es SVD-spezifische Iterationsmethoden gibt. zB Augmented Implicitly Restarted Lanczos Bidiagonalization Methods , J. Baglama und L. Reichel, SIAM J. Sci. Comput. 2005. (Ich habe das Papier nicht gelesen, um zu wissen, ob es sich grundlegend von dem Eigenwertansatz unterscheidet, den Sie angegeben haben. Wissen Sie nur, dass die Leute diese Methode mögen.)

Dougal

Danke für den Link, @Dougal. Ich sollte sagen, dass ich keine dieser Methoden wirklich gut kenne, also kann ich das nicht wirklich kommentieren. Es wäre großartig, wenn jemand, der sich besser auskennt, die Beziehung zwischen verschiedenen iterativen Methoden erklären würde. Soweit ich weiß, dient die Vanille-Lanczos-Methode zur Berechnung von Eigenwerten einer quadratischen Matrix und nicht zur SVD. "Augmented Implicit Restarted Lanczos" sollte eng damit verwandt sein, aber Sie haben Recht - es scheint sich direkt um SVD zu handeln. Ich bin nicht sicher, wie alles zusammenpasst. Ich werde meine Antwort aktualisieren, wenn ich sie mir näher anschaue.

Amöbe sagt Reinstate Monica

@Dougal, ich habe etwas flüchtig gelesen und ein Update gemacht.

Amöbe sagt Reinstate Monica

@amoeba wäre "abgeschnittene SVD" im Zusammenhang mit regulierten kleinsten Quadraten im Wesentlichen dasselbe wie "Regression der Hauptkomponenten" ?

GeoMatt22

@amoeba Kannst du die zufällige SVD-Implementierung von Facebook kommentieren? Einige Leute scheinen zu sagen, dass es momentan zu den schnellstmöglichen Lösungen gehört. Es wäre großartig, wenn Sie auch dies bearbeiten und kommentieren könnten.

Tim

Ich bin gerade über googeln-schnelle SVDs auf den Thread gestoßen, also versuche ich, die Dinge selbst herauszufinden, aber vielleicht sollten Sie sich mit adaptiver Kreuzapproximation (ACA) befassen.

$M$ $M=\sum_{i=0}^k U_i\cdot V^T_i$ $N\times N$ $O(N)$

Auch hier hängt es von Ihrem Problem ab, ob das funktioniert. In vielen Fällen, die mir persönlich begegnen, ist der ACA ein sehr nützliches numerisches Werkzeug.

Hinweis: Ich wollte dies als Kommentar schreiben, aber da ich gerade diesen Account erstellt habe, habe ich nicht genug Ruf für Kommentare ... Aber das Posten funktioniert.

oli
quelle

Hier ist eine Technik, die ich in der Vergangenheit erfolgreich zum Berechnen einer abgeschnittenen SVD (im Netflix-Datensatz) verwendet habe. Es ist aus diesem Papier entnommen . Bei einer kollaborativen Filtereinstellung sollte beachtet werden, dass die meisten Werte fehlen, und der Punkt ist, sie vorherzusagen. Um also eine abgeschnittene SVD zu verwenden, um ein solches Problem zu lösen, müssen Sie eine Technik verwenden, die unter diesen Bedingungen funktioniert. Eine kurze Beschreibung:

Bevor Sie etwas tun, passen Sie ein einfaches Modell an (z. B. globale Mittelwerte + Spalten- und Zeilenkonstantenwerte). Wenn Sie dies getan haben, sollten Sie die abgeschnittene SVD verwenden, um die Residuen anzupassen.
Initialisieren Sie einen Zufallsvektor der Länge k (wobei dies der Rang ist, auf den Sie kürzen) für jede Zeile und Spalte (für jeden Film und jeden Benutzer im Netflix-Fall).
Halten Sie die Zeilenvektoren fest und aktualisieren Sie die Spaltenvektoren, um Fehler in Bezug auf die bekannten Einträge in der Matrix zu minimieren . Die Vorgehensweise ist im Matlab-Code im Papier angegeben.
Halten Sie die Spaltenvektoren fest und aktualisieren Sie die Zeilenvektoren auf analoge Weise.
Wiederholen Sie 3 & 4, bis Sie konvergieren oder gute Ergebnisse erzielen.

Stumpy Joe Pete
quelle