Aktualisieren der SVD-Zerlegung nach dem Hinzufügen einer neuen Zeile zur Matrix

Angenommen, ich habe eine dichte Matrix der Größe und der SVD-ZerlegungIn ich die SVD berechnen sich wie folgt: . $\textbf{A}$ $m \times n$

EIN = {U S V}^{⊤} .

$\mathbf{A}=\mathbf{USV}^\top.$ Rsvd(A)

Wenn eine neue -te Zeile zu hinzugefügt wird , kann man die neue SVD-Zerlegung basierend auf der alten (dh unter Verwendung von , und ) ohne Neuberechnung berechnen SVD von Grund auf neu? $(m+1)$ $\mathbf A$ $\mathbf U$ $\mathbf S$ $\mathbf V$

algorithms svd linear-algebra matrix-decomposition numerics user1436187
quelle

Überprüfen Sie die Literatur von rank 1 updates. Schnelle Online-SVD-Revisionen für leichte Empfehlungssysteme von Brand sind ein zugängliches erstes Papier. Ich habe leider noch nichts für SVD in R implementiert gesehen. Dank CHOLMOD gibt es ( updownvon Matrix) Cholesky-Updates . Die Sparsamkeit Ihrer Matrix sich wirklich von Ihrer endgültigen Lösung. Nehmen Sie eine dichte oder eine spärliche Matrix an?

A

$A$

usεr11852 sagt Reinstate Monic

+1 an @ usεr11852. Beachten Sie auch, dass das Aktualisieren von QR viel einfacher und standardmäßiger ist und in einigen Anwendungen QR ausreicht und man SVD nicht wirklich benötigt. Denken Sie also auch an Ihre Bewerbung.

Amöbe sagt Reinstate Monica

Ja, die Matrix ist dicht.

user1436187

Lassen Sie die empfohlene Literatur los und konzentrieren Sie sich auf die Bildverarbeitung. Ähnliche Fragen mit Touren wurden in Bezug auf "neue Bilder" in einer Datenbank veröffentlicht. Meine Vermutung ist zum Beispiel, dass jemand einen Algorithmus haben muss, um die Einträge seiner Eigengesichter online zu aktualisieren. Diese Leute arbeiten mit dichten Matrixdarstellungen.

usεr11852 sagt Reinstate Monic

Einige verwandte Themen auf anderen SE-Websites: scicomp.stackexchange.com/questions/2678 , scicomp.stackexchange.com/questions/19253 , mathoverflow.net/questions/143375 .

Amöbe sagt Reinstate Monica

Ja, eine SVD-Zerlegung kann aktualisiert werden, nachdem der vorhandenen Matrix eine neue Zeile hinzugefügt wurde.

Im Allgemeinen wird diese Problemformulierung " Add One To " als Rang-1-Aktualisierung bezeichnet . Der von @amoeba bereitgestellte MathOverflow-Link zum Thema " Effiziente Rang-2-Aktualisierungen einer Eigenwertzerlegung " ist ein guter erster Schritt, wenn Sie sich eingehender mit der Materie befassen möchten. Das erste Papier bietet eine explizite Lösung für Ihre spezifische Frage. Nur um zu klären, was Rang eins und Rang zwei bedeuten, damit Sie nicht verwirrt werden, wenn Ihr neues ist, dass: $A^*$

\begin{aligned} A^{*} = A - u v^{T} \end{aligned}

$\begin{align} A^* = A - uv^T \end{align}$

Wenn und Vektoren sind, wird dies als Rang-1-Aktualisierung (oder Störung ) bezeichnet. Die Grundlagen dieses Updates werden durch die Sherman-Morrison-Formel vorgegeben . . Wenn die Störung mehr als einen Rang hat, d. $u$ $v$

\begin{aligned} {EIN}^{*} = EIN - U V^{T} \end{aligned}

$\begin{align} A^* = A - UV^T \end{align}$

Die Woodbury-Formel kommt ins Spiel. Wenn Sie diese Formeln sehen, werden Sie feststellen, dass es sich um viele inverse Formeln handelt. Sie lösen diese nicht direkt. Da Sie bereits viele ihrer Subsysteme gelöst haben (dh Sie haben bereits eine gewisse Zerlegung berechnet), verwenden Sie diese, um schnellere und / oder stabilere Schätzungen zu erhalten. (Deshalb forschen die Leute immer noch auf diesem Gebiet.) Ich habe das Buch " Computational Statistics " von JE Gentle oft als Referenz verwendet. Ich denke, Kap. 5 Die numerische lineare Algebra richtet Sie richtig ein. (Der Überklassiker: " Matrix-Algebra aus Sicht eines Statistikers " von Harville geht leider überhaupt nicht auf Rangaktualisierungen ein .)

Auf der Statistik- / Anwendungsseite sind Rang-1-Aktualisierungen in Empfehlungssystemen üblich, da möglicherweise Tausende von Kundeneinträgen vorhanden sind und die SVD (oder eine bestimmte Zerlegung in diesem Fall) jedes Mal neu berechnet werden, wenn sich ein neuer Benutzer registriert oder ein neues Produkt registriert hinzugefügt oder entfernt ist ziemlich verschwenderisch (wenn nicht unerreichbar). In der Regel sind empfehlenswerte Systemmatrizen spärlich, was die Algorithmen noch effizienter macht. Ein zugängliches erstes Papier ist das Manuskript " Schnelle Online-SVD-Überarbeitungen für leichte Empfehlungssysteme " von M. Brand. Bei dichten Matrizen denke ich, dass ein Blick auf die Arbeiten von Pattern Recognition and Imaging Processing Sie ziemlich weit bringen kann, einen tatsächlichen Algorithmus zu verwenden. Zum Beispiel die Papiere:

Inkrementelles Lernen von bidirektionalen Hauptkomponenten für die Gesichtserkennung (2009) von Ren und Dai,
Zum inkrementellen und robusten Subraumlernen (2003) von Li et al.
Sequentielle Karhunen-Loeve-Basisextraktion und ihre Anwendung auf Bilder (2000) von Levey und Lindenbaum.
Inkrementelles Lernen für robustes visuelles Tracking (2007) von Ross et al.

alle scheinen das gleiche Problem in ihrem Kern anzugehen; Neue Funktionen sind hinzugekommen und wir müssen unsere Darstellung entsprechend schnell aktualisieren . Beachten Sie, dass diese Matrizen nicht symmetrisch oder sogar quadratisch sind. Eine andere Arbeit von M. Brand kann sich ebenfalls mit diesem Problem befassen (siehe den Aufsatz " Schnelle Modifikationen der Zerlegung dünner Singulärwerte in niedrigen Rängen (2006) " - dies wurde auch in dem am Anfang des Beitrags angegebenen MO-Link erwähnt.) Dort a Viele großartige Artikel zu diesem Thema, aber die meisten sind in der Regel stark mathematisch (z. B. die Artikel von Benaych-Georgesa und Nadakuditi zu " Die singulären Werte und Vektoren von Störungen mit niedrigem Rang von großen rechteckigen Zufallsmatrizen" (2012).") und ich glaube nicht, dass sie bald zu einer Lösung führen werden. Ich würde vorschlagen, dass Sie sich weiterhin auf die Bildverarbeitungsliteratur konzentrieren.

Leider bin ich auf keine R-Implementierungen für Rang-1-Aktualisierungsroutinen gestoßen. Die Antwort auf " Aktualisierbare SVD-Implementierung in Python, C oder Fortran? " Der Computational Science SE enthält eine Reihe von MATLAB- und C ++ - Implementierungen, die Sie in Betracht ziehen können. In der Regel handelt es sich bei der Implementierung von R, Python usw. um Wrapper für C-, C ++ - oder FORTRAN-Implementierungen.

usεr11852 sagt Reinstate Monic
quelle

Dies ist ein netter Kommentar, aber ich war enttäuscht, keine Antwort auf die Frage zu finden. Es stellt sich heraus, dass ein anderes Papier von Matthew Brand , auf das die Antwort von MO verweist, eine explizite Lösung enthält.

whuber

+1 sowohl an Sie als auch an @whuber (und ich denke nicht, dass das "Duplizieren" von Informationen, die auf einer anderen SE-Site bereitgestellt werden, zu vermeiden ist! Ich würde argumentieren, dass wir versuchen sollten, die auf dieser Site bereitgestellten Informationen als eigenständig zu gestalten Tatsächlich duplizieren fast alle hier enthaltenen Informationen in gewisser Weise vorhandene Lehrbücher, Online-Ressourcen oder Forschungsarbeiten. Eine Frage: Sie haben Sherman-Morrison- und Woodbury-Formeln erwähnt, die beschreiben, wie sich die Inverse der Matrix nach einem Rang-1-Update oder einem Update mit höherem Rang ändert. was haben sie mit SVD zu tun?

Amöbe sagt Reinstate Monica

Ich verstehe, warum Sie Leute zu den MO-Seiten für diesen Link leiten möchten, aber Sie könnten direkt darüber nachdenken, zu behaupten, dass dies das Problem löst! ("Ein guter erster Schritt" ist eine große Untertreibung.) Ein Großteil Ihrer Kommentare könnte als Hinweis darauf missverstanden werden, dass Sie noch keine gute Lösung gefunden haben.

whuber

@whuber: "Gut" wurde "großartig" und jetzt habe ich auch die Zeitung erwähnt, besser? :) (Danke übrigens für das Feedback.)

usεr11852 sagt Reinstate Monic

Nur der Geschichte zuliebe: Bunch und Nielsen waren die ersten, die einen Weg zeigten, die SVD zu aktualisieren und zu downdieren. Die Methode von Brand verallgemeinert die Methoden dieses älteren Papiers.

JM ist kein Statistiker

Aktualisieren der SVD-Zerlegung nach dem Hinzufügen einer neuen Zeile zur Matrix

Antworten: