Was sind effiziente Algorithmen zur Berechnung der Singularwertzerlegung (SVD)?

17

Der Wikipedia-Artikel zur Hauptkomponentenanalyse besagt dies

Es gibt effiziente Algorithmen zur Berechnung der SVD von ohne dass die Matrix muss. Daher ist die Berechnung der SVD heute die Standardmethode zur Berechnung einer Hauptkomponentenanalyse aus einer Datenmatrix, sofern nicht nur eine Handvoll Komponenten erforderlich sind.XXTX

Könnte mir jemand sagen, um welche effizienten Algorithmen es sich in dem Artikel handelt? Es wird kein Verweis angegeben (eine URL oder ein Verweis auf einen Artikel, der diese Art der Berechnung vorschlägt, wäre nett).

pca algorithms svd numerics svd
quelle
4
Eine Google-Suche zum Singular-Value-Dekompositionsalgorithmus hebt relevante Informationen hervor.
Whuber
1
Vergessen Sie nicht, den Mittelwert vor SVD für PCA zu entfernen!
Memming
Probieren Sie Lanczos SVD!
Ciri

Antworten:

12

Das Hauptarbeitspferd hinter der Berechnung der SVD ist der QR-Algorithmus . Allerdings gibt es viele verschiedene Algorithmen, um die Singulärwertzerlegung einer generischen by- N- Matrix A zu berechnen . Ein großartiger Schaltplan zu diesem Thema finden Sie hier (aus der Dokumentation von Intel)MNEIN MKL ) ist die folgende:Bildbeschreibung hier eingeben

Wie Sie sehen, gibt es je nach Anwendungsfall unterschiedliche Ansätze (die Namenskonventionen für Routinen finden Sie hier ). Das liegt zum Beispiel daran, dass es Matrixformulare gibt, bei denen eine Reduzierung der Haushaltsinhaber teurer sein kann als eine Givens-Rotation (um nur zwei "offensichtliche" Wege zu nennen, QR zu erhalten). Ein Standardwerk über die Angelegenheit ist Golub und Van Loan der Matrix Computations (Ich würde die 3. Auflage zumindest empfehlen die Verwendung). Ich habe auch Å gefunden. Björcks numerische Methoden für Kleinste-Quadrate-Probleme in dieser Hinsicht eine sehr gute Ressource; Obwohl SVD nicht der Hauptfokus des Buches ist, hilft es bei der Kontextualisierung seiner Verwendung.

Wenn ich Ihnen einen allgemeinen Rat zu diesem Thema geben muss, versuchen Sie nicht, Ihre eigenen SVD-Algorithmen zu schreiben, es sei denn, Sie haben bereits einige Kurse zur numerischen linearen Algebra erfolgreich absolviert und wissen, was Sie tun. Ich weiß, dass es sich kontraintuitiv anhört, aber es gibt eine Menge Dinge, die schief gehen können und bei denen Sie (bestenfalls) suboptimale Implementierungen erzielen (wenn nicht sogar falsch). Es gibt einige sehr gute kostenlose Suiten zu diesem Thema (zB Eigen , Armadillo und Trilinos, um nur einige zu nennen.)

usεr11852 sagt Reinstate Monic
quelle
XEIN
1
MNEINXTX
2
Ja, ich habe mich geirrt: QR ist nicht auf quadratische Matrizen beschränkt. +1 übrigens. Diese Frage war eine der am höchsten bewerteten unbeantworteten Fragen mit dem pca- Tag, daher ist es schön zu sehen, dass sie endlich beantwortet wurde.
Amöbe sagt Reinstate Monica
Ihre Antwort erwähnt nicht eine ganze Reihe von iterativen Algorithmen. War es absichtlich? Jemand hat eine Frage zu iterativen SVD-Algorithmen gestellt. Siehe Welche schnellen Algorithmen gibt es für die Berechnung von abgeschnittener SVD? , und ich habe dort eine Antwort gepostet, um einen Überblick zu geben. Vielleicht sollten wir zumindest unsere Antworten miteinander verknüpfen. Und es wäre sicherlich großartig, wenn Sie Ihre Möglichkeiten durch eine Diskussion von QR-Algorithmen und iterativen Algorithmen erweitern könnten.
Amöbe sagt Reinstate Monica
Nein, es war zufällig. Sie haben Ihre eigene Frage in Ihrem Beitrag beantwortet. Verkürzte SVD sind im Wesentlichen verkürzte eigendecompositions (siehe zum Beispiel ARPACK ). Es gibt einige feine Unterschiede, aber sie sind in Ordnung ; Einige Software (z. B. svdsMATLABs eigs) verwenden einfach ihre abgeschnittene SVD-Funktion als Wrapper für ihre abgeschnittenen eigendecomposition ( ) -Routinen.
usεr11852 sagt Reinstate Monic