Wie wird die SVD einer Matrix in der Praxis berechnet?

Wie berechnet MATLAB beispielsweise die SVD einer bestimmten Matrix? Ich gehe davon aus, dass die Antwort wahrscheinlich die Berechnung der Eigenvektoren und Eigenwerte von beinhaltet A*A'. Wenn das der Fall ist, würde ich auch gerne wissen, wie es diese berechnet?

Dies geschieht normalerweise mit dem Golub-Reinsch-Algorithmus, und nein, es werden keine Eigenwerte und Eigenvektoren von berechnet . $AA^{T}$

Sehen

GH Golub und C. Reinsch. Singular Value Decomposition- und Least Squares-Lösungen. Numerische Mathematik 14: 403 & ndash; 420, 1970.

Dieses Material wird in vielen Lehrbüchern zur numerischen linearen Algebra diskutiert.

Abgesehen von dem (jetzt klassischen) Golub-Reinsch-Papier, das Brian in seiner Antwort notiert (ich habe auf die Handbuchversion des Papiers verwiesen), sowie dem (ebenfalls jetzt klassischen) Vorgängerpapier von Golub-Kahan , gab es eine Reihe von wichtigen Entwicklungen bei der Berechnung der SVD seitdem. Zunächst muss ich zusammenfassen, wie die übliche Methode funktioniert.

Die Idee bei der Berechnung der SVD einer Matrix ist qualitativ ähnlich zu der Methode, die zur Berechnung der Eigenzerlegung einer symmetrischen Matrix verwendet wird (und wie im OP erwähnt, besteht eine enge Beziehung zwischen ihnen). Insbesondere erfolgt man in zwei Schritten: der Transformation in eine bidiagonale Matrix und dem Auffinden der SVD einer bidiagonalen Matrix. Dies ist völlig analog zu dem Verfahren, bei dem zuerst eine symmetrische Matrix auf eine tridiagonale Form reduziert und dann die Eigenzerlegung der resultierenden Tridiagonale berechnet wird.

Ein besonders interessanter Durchbruch für die Berechnung der SVD einer bidiagonalen Matrix war das Papier von Jim Demmel und Velvel Kahan , das zeigte, dass man selbst die winzigen Singularwerte einer bidiagonalen Matrix mit guter Genauigkeit berechnen kann, indem man die ursprünglich in Golub-Reinsch. Dies wurde dann gefolgt von der (Wieder-?) Entdeckung des dqd Algorithmus , der ein Nachkomme des alten Quotienten-Differenz - Algorithmus von Rutishauser ist. (Beresford Parlett gibt eine nette Diskussion hier.) Wenn Speicher dient, ist dies jetzt die bevorzugte Methode, die intern von LAPACK verwendet wird. Abgesehen davon war es immer möglich, SVD-Versionen von Entwicklungen bei der Lösung symmetrischer Eigenprobleme abzuleiten. Zum Beispiel gibt es eine SVD-Version von Divide-and-Conquer sowie eine SVD-Version des alten Jacobi-Algorithmus (die unter bestimmten Umständen genauer sein kann).

In Bezug auf die Bidiagonalisierung wurde in Barlows Artikel eine verbesserte Methode beschrieben , die etwas mehr Arbeit erfordert als das ursprüngliche Verfahren von Golub und Reincsh, aber genauere bidiagonale Matrizen liefert.