Wie ist der aktuelle Stand der Technik bei Algorithmen zur Singularwertzerlegung?

Ich arbeite an einer Nur-Header-Matrixbibliothek, um einen angemessenen Grad an linearer Algebra in einem möglichst einfachen Paket bereitzustellen, und ich versuche, einen Überblick über den aktuellen Stand der Technik zu erhalten: die SVD von a komplexe Matrix.

Ich mache eine zweiphasige Zerlegung, Bidiagonalisierung, gefolgt von einer Berechnung des Singularwerts. Im Moment verwende ich die Householder-Methode für die Bidiagonalisierung (ich glaube, LAPACK verwendet diese Methode auch), und ich denke, das ist ungefähr so ​​gut wie es derzeit ist (es sei denn, jemand kennt einen -Algorithmus dafür.) . $\mathcal{O}(N^2)$

Die Singularwertberechnung steht als nächstes auf meiner Liste, und ich bin ein wenig unschlüssig, was die üblichen Algorithmen dafür sind. Ich habe hier gelesen , dass die Forschung auf eine inverse Iterationsmethode zusteuerte, die Orthogonalität mit -Komplexität garantiert . Ich würde gerne davon oder von anderen Fortschritten erfahren.$\mathcal{O}(N)$

"Randomisierte Algorithmen" sind in letzter Zeit für Teil-SVDS recht populär geworden. Eine Implementierung nur für Header kann hier heruntergeladen werden: http://code.google.com/p/redsvd/

Eine Übersicht über die aktuellen Methoden finden Sie hier: http://arxiv.org/abs/0909.4061

Für volle svds bin ich mir nicht sicher, ob du es besser kannst als Householder.

$\mathcal{O}(N)$

(Ich wollte nur ein paar Kommentare machen, da ich nicht die Zeit habe, Details zu schreiben, aber es wurde ziemlich groß für das Kommentarfeld.)

$\mathbf L\mathbf D\mathbf L^\top$$\mathbf U\mathbf D\mathbf U^\top$

Der "Singularwert" -Abschnitt des Algorithmus stammt hingegen vom (verschobenen) Differentialquotientendifferenz-Algorithmus (dqd (s)) , der eine Zusammenfassung früherer Arbeiten von Fernando, Parlett , Demmel und Kahan (mit Inspiration) ist von Heinz Rutishauser).

Wie Sie vielleicht wissen, werden SVD-Methoden in der Regel zuerst mit einer bidiagonalen Zerlegung fortgesetzt, bevor die Singularwerte aus der bidiagonalen Matrix erhalten werden. Leider bin ich nicht über die derzeit beste Methode für die bidiagonale Front-End-Zerlegung informiert. Als letztes habe ich überprüft, dass die übliche Methode darin besteht, mit der QR-Zerlegung mit Säulendrehung zu beginnen und dann orthogonale Transformationen entsprechend auf den Dreiecksfaktor anzuwenden, um schließlich die bidiagonale Zerlegung zu erhalten.

Ich verstehe, dass ich mit den Details knapp war; Ich werde versuchen, diese Antwort weiter zu konkretisieren, sobald ich Zugang zu meiner Bibliothek habe ...

Es gibt die Bibliotheken PROPACK und nu-TRLan.

http://soi.stanford.edu/~rmunk/PROPACK/

http://crd-legacy.lbl.gov/~kewu/trlan/