Grundlegende Arbeiten zu Matrixzerlegungen

18

Ich habe kürzlich Skillicorns Buch über Matrixzerlegungen gelesen und war ein bisschen enttäuscht, da es sich an ein junges Publikum richtete. Ich möchte (für mich und andere) eine kurze Bibliographie wesentlicher Arbeiten (Umfragen, aber auch bahnbrechende Arbeiten) zu Matrixzerlegungen zusammenstellen. Was ich in erster Linie im Auge habe, ist etwas über SVD / PCA (und robuste / spärliche Varianten) und NNMF, da diese bei weitem am häufigsten verwendet werden. Haben Sie alle eine Empfehlung / einen Vorschlag? Ich halte mich zurück, um die Antworten nicht zu voreingenommen zu machen. Ich würde bitten, jede Antwort auf 2-3 Papiere zu beschränken.

PS: Ich bezeichne diese beiden Zerlegungen als die in der Datenanalyse am häufigsten verwendeten . Natürlich sind QR, Cholesky, LU und Polar in der numerischen Analyse sehr wichtig. Das ist jedoch nicht der Schwerpunkt meiner Frage.

matrix-decomposition svd numerics zufrieden
quelle

Antworten:

16

Woher wissen Sie, dass SVD und NMF bei weitem die am häufigsten verwendeten Matrixzerlegungen sind und nicht LU, Cholesky und QR? Mein persönlicher Lieblingsdurchbruch müsste der garantierte rangaufschlussreiche QR-Algorithmus sein.

  • Chan, Tony F. "Rang enthüllt QR-Faktorisierungen". Lineare Algebra und ihre Anwendungsbände 88-89, April 1987, Seiten 67-82. DOI: 10.1016 / 0024-3795 (87) 90103-0

... eine Weiterentwicklung der früheren Idee von QR mit Column-Pivoting:

  • Businger, Peter; Golub, Gene H. (1965). Lineare Least Squares-Lösungen durch Householder-Transformationen. Numerische Mathematik Band 7, Nummer 3, 269-276, DOI: 10.1007 / BF01436084

A ( das ?) Klassische Lehrbuch:

  • Golub, Gene H; Van Loan, Charles F. (1996). Matrix Computations (3. Aufl.), Johns Hopkins, ISBN 978-0-8018-5414-9 .

(Ich weiß, dass du nicht nach Lehrbüchern gefragt hast, aber ich kann nicht widerstehen.)

Bearbeiten: Ein bisschen mehr googeln findet ein Papier, dessen Zusammenfassung darauf hindeutet, dass wir leicht an Schweinswalen sind. Der obige Text stammt aus der Perspektive der 'numerischen linearen Algebra' (NLA). Möglicherweise beschäftigen Sie sich mehr mit der Perspektive der angewandten Statistik / Psychometrie (AS / P)? Könnten Sie vielleicht klarstellen?

Stopp
quelle
2
Ich würde "das" Lehrbuch selbst sagen, wobei Stewarts Matrix-Algorithmen ( beide Teile ) einen knappen zweiten Platz einnehmen. Ich würde selbst eine Liste der bahnbrechenden Veröffentlichungen geben, aber das OP sollte wirklich erklären, ob er den Standpunkt der Zahlen oder den Standpunkt der Statistiken will (ich kann beim ersteren helfen, aber nicht so sehr beim letzteren).
JM ist kein Statistiker
1
+1 für Golub und Van Loan. Und ja, der endgültige Artikel ist angemessen.
Shabbychef
2
Ich habe meine Frage bearbeitet, um zu verdeutlichen, dass ich mich auf den Statistik-Teil konzentriere. Ich stimme allen zu, dass Golub und Van Loan die Standardreferenz für Matrixzerlegungen sind. Das Thema der Zerlegung in sehr großem Maßstab durch zufällige Projektionen wird jedoch ausgelassen. Ein Übersichtsartikel, den ich in meine Liste aufnehmen würde, ist "Struktur mit Zufälligkeit finden: Stochastische Algorithmen zur Konstruktion angenäherter Matrixzerlegungen" von Halko et al.
gappy
4

Lee und Seung beschreiben für NNMF einen iterativen Algorithmus, der sehr einfach zu implementieren ist. Tatsächlich geben sie zwei ähnliche Algorithmen an, einen zur Minimierung der Frobenius-Norm des Residuums und einen zur Minimierung der Kullback-Leibler-Divergenz der Approximation und der ursprünglichen Matrix.

shabbychef
quelle
3

Vielleicht findest du interessant

  1. [Lernen mit Matrixfaktorisierungen ] Doktorarbeit von Nathan Srebro,
  2. [Untersuchung verschiedener Matrixfaktorisierungsmethoden für große Empfehlungssysteme] , Gábor Takács et al. und fast die gleiche Technik wie hier beschrieben

Die letzten beiden Links zeigen, wie spärliche Matrix-Faktorisierungen in Collaborative Filtering verwendet werden. Ich glaube jedoch, dass SGD-ähnliche Faktorisierungsalgorithmen an anderer Stelle nützlich sein können (zumindest sind sie extrem einfach zu codieren).

3 Umdrehungen
quelle
2

Witten, Tibshirani - Bestrafte Matrixzerlegung

http://www.biostat.washington.edu/~dwitten/Papers/pmd.pdf

http://cran.r-project.org/web/packages/PMA/index.html

Martinsson, Rokhlin, Szlam, Tygert - Randomisierte SVD

http://cims.nyu.edu/~tygert/software.html

http://cims.nyu.edu/~tygert/blanczos.pdf

pro Scheibe
quelle
5
Vielen Dank. Ich kenne beide Papiere. Ich bin kein großer Fan von Witten [nicht Whitten] et al., Da ich denke, dass es wichtigere Artikel über spärliche Zersetzungen gibt. In Bezug auf randomisierte SVD gefällt mir besonders die Übersichtsarbeit "Struktur mit Zufälligkeit finden: Stochastische Algorithmen zur Konstruktion von ungefähren Matrixzerlegungen" ( arxiv.org/abs/0909.4061 ), die auch von Martinsson mitverfasst wurde.
gappy
Genau. Ich habe gerade zwei Papiere herausgebracht, die niemand erwähnt hatte.
Pslice
2

Auf dem diesjährigen NIPS gab es einen kurzen Artikel über verteilte, sehr umfangreiche SVDs, die in einem Durchgang über eine Streaming-Eingangsmatrix arbeiten .

Das Papier ist eher umsetzungsorientiert, ordnet die Dinge jedoch in Bezug auf die tatsächlichen Uhrzeiten und alles andere in die richtige Perspektive ein. Die Tabelle am Anfang ist auch eine gute Übersicht.

pisk
quelle
Wofür steht NIPS?
am
@onestop Link hinzugefügt. NIPS = Neuronale Informationsverarbeitungssysteme. Es ist eine Community (kein System :)). Aber Pisk spricht über die Konferenz NIPS 2010.
Robin Girard