Berechnen der abgeschnittenen SVD, jeweils ein Singularwert / Vektor

11

Gibt es einen abgeschnittenen SVD-Algorithmus, der die Singularwerte einzeln berechnet?

Mein Problem: Ich möchte die ersten k Singularwerte (und Singularvektoren) einer großen dichten Matrix berechnen M, weiß aber nicht, was ein geeigneter Wert von k wäre. M ist groß, daher würde ich aus Effizienzgründen die vollständige SVD lieber nicht auswerten, um anschließend die kleinsten SVs abzuschneiden.

Idealerweise gibt es eine Möglichkeit, die Singularwerte σ1,σ2, seriell vom größten ( σ1 ) zum kleinsten ( σn ) zu berechnen . Auf diese Weise könnte ich die Berechnung nach Berechnung des k ten Singularwerts einfach anhalten, wenn σk/σ1 unter einen bestimmten Schwellenwert fällt.

Gibt es einen solchen Algorithmus (vorzugsweise mit einer Python-Implementierung)? Beim Googeln habe ich nur abgeschnittene SVD-Funktionen gefunden, die k als Parameter verwenden, sodass Sie gezwungen sind, dies a priori zu erraten.

SuperElectric
quelle
Ist dein M quadratisch oder rechteckig? Wenn rechteckig, möchten Sie die langen oder kurzen singulären Vektoren? Das heißt, wenn M (mxn) mit m> n ist, möchten Sie (mxk) oder (kxn)?
Max Hutchinson
M ist rechteckig mit viel mehr Zeilen als Spalten. Ich möchte die kurzen singulären Vektoren (dh V in M ​​= U S V ^ T).
SuperElectric

Antworten:

6

Es stehen einige Optionen zur Verfügung, wenn Sie eine ungefähre Rang-k-Faktorisierung wünschen.

  1. Stark rangaufschlussreiche QR-Faktorisierungen
  2. Interpolative Zerlegung (ID) und andere randomisierte Techniken.

AMNTfactor×σk+1(A):=ϵ

Eine ungefähre Faktorisierung der obigen Form kann unter Verwendung von Standardtechniken in eine Standardzerlegung wie QR oder SVD umgewandelt werden. Eine gute Übersicht finden Sie in dem Artikel von Halko, Martinsson und Tropp "Struktur mit Zufälligkeit finden: Probabilistische Algorithmen zur Konstruktion von ungefähren Matrixzerlegungen".

In Bezug auf die Software steht in scipy (scipy.linalg.interpolative) http://docs.scipy.org/doc/scipy-dev/reference/linalg.interpolative.html eine Schnittstelle zu ID-Algorithmen zur Verfügung , über die der Benutzer angeben kann .ϵ

user2457602
quelle
2

(Bearbeitet, weil ich die Frage zuerst falsch verstanden habe; Sie wissen bereits, dass Routinen zur Berechnung der ersten Singularwerte verfügbar sind.)k

Wenn Sie den Ansatz der Berechnung der gesamten SVD ausschließen, reduzieren sich partielle SVD-Algorithmen auf die Verwendung iterativer Methoden zur Lösung eines verwandten hermitischen Eigenwertproblems. Eine Strategie, die Sie verfolgen könnten, wäre, diese Art von Dingen selbst von Hand zu codieren und so lange nach dem größten verbleibenden ungelösten Singularwert zu suchen, bis Sie aufhören möchten, indem Sie so etwas wie eine Shift-and-Invert-Strategie verwenden. In anspruchsvollen Paketen wie SLEPc gibt es möglicherweise elegante Möglichkeiten, dies zu tun .

Eine andere Strategie wäre die folgende:

  • Berechnen Sie den größten Singularwert .s1
  • Setzen Sie die absolute Toleranz der spärlichen SVD-Routine auf , wobei Ihr Schwellenwert ist und ein Sicherheitsfaktor ist, um zu bestimmen, wie viele möglicherweise fremde Singularwerte Sie möchten berechnen.τs1fτ0<f1
  • Rufen Sie die spärliche SVD-Routine auf.

Wenn die spärliche SVD-Routine eine dünne SVD berechnet (und ich kann nicht verstehen, warum dies nicht der Fall ist), erhalten Sie mit dieser Strategie alle gewünschten Singularwerte (plus möglicherweise einige zusätzliche), da Werte unterhalb der absoluten Toleranz angezeigt werden als Null behandelt werden. In diesem Fall können Sie scipy.sparse.linalg.svds verwenden und dabei beachten , dass ein optionaler Parameter ist und Sie ihn nicht a priori angeben müssen .k

Geoff Oxberry
quelle
Wenn Sie in scipy.sparse.linalg.svds nicht 'k' angeben, wird unabhängig vom Parameter 'tol' standardmäßig k = 6 verwendet. Es ist nicht klar, ob dies ein Fehler ist oder ob sich 'tol' auf die Genauigkeit der berechneten Singularwerte (und nicht auf deren Größe) beziehen soll
Nick Alger