Niezbędne artykuły na temat rozkładu macierzy

18

Niedawno przeczytałem książkę Skillicorn o rozkładach matryc i byłem nieco rozczarowany, ponieważ był skierowany do słuchaczy. Chciałbym skompilować (dla siebie i innych) krótką bibliografię podstawowych artykułów (ankiety, ale także artykuły przełomowe) na temat rozkładu macierzy. Mam przede wszystkim na myśli SVD / PCA (i mocne / rzadkie warianty) i NNMF, ponieważ są one najczęściej używane. Czy wszyscy macie jakieś rekomendacje / sugestie? Powstrzymuję moje, by nie stronić od odpowiedzi. Prosiłbym o ograniczenie każdej odpowiedzi do 2-3 artykułów.

PS: Te dwa dekompozycje nazywam najczęściej stosowanymi w analizie danych . Oczywiście QR, Cholesky, LU i polar są bardzo ważne w analizie numerycznej. Nie na tym jednak koncentruje się moje pytanie.

matrix-decomposition svd numerics zadowolony
źródło

Odpowiedzi:

16

Skąd wiesz, że SVD i NMF są zdecydowanie najczęściej stosowanymi rozkładami macierzy, a nie LU, Cholesky i QR? Moim ulubionym „przełomem” musiałby być gwarantowany algorytm QR ujawniający rangę,

  • Chan, Tony F. „Pozycja ujawniająca faktoryzacje QR”. Algebra liniowa i jej zastosowania, tomy 88–89, kwiecień 1987, strony 67–82. DOI: 10.1016 / 0024-3795 (87) 90103-0

... rozwinięcie wcześniejszego pomysłu QR z obrotową kolumną:

  • Businger, Peter; Golub, Gene H. (1965). Liniowe rozwiązania najmniejszych kwadratów według transformacji Householdera. Numerische Mathematik Volume 7, Number 3, 269-276, DOI: 10.1007 / BF01436084

A ( ?) Klasyczny podręcznik jest:

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

(wiem, że nie prosiłeś o podręczniki, ale nie mogę się oprzeć)

Edycja: Nieco więcej googlingów znajduje artykuł, którego streszczenie sugeruje, że możemy być nieco w poprzek morświnów. Mój powyższy tekst pochodzi z perspektywy „numerycznej algebry liniowej” (NLA); być może bardziej interesuje Cię perspektywa „statystyki stosowanej / psychometrii” (AS / P)? Czy mógłbyś to wyjaśnić?

onestop
źródło
2
Powiedziałbym sam „podręcznik”, a algorytmy Matrix Stewarta ( obie części ) są na drugim miejscu. Osobiście dałbym listę prac pionierskich, ale OP naprawdę powinien wyjaśnić, czy chce punktu widzenia liczbowego lub statystycznego (mogę pomóc z tym pierwszym, ale nie tak bardzo drugim).
JM nie jest statystykiem
1
+1 dla Golub i Van Loan. I tak, ostateczny artykuł jest odpowiedni.
shabbychef
2
Zredagowałem swoje pytanie, aby wyjaśnić, że skupiam się na części dotyczącej statystyki. Zgadzam się ze wszystkimi, że Golub i Van Loan są standardowymi wzorcami dla rozkładu macierzy. Ale pomija temat rozkładu na bardzo dużą skalę za pomocą losowych projekcji. Artykuł, który chciałbym umieścić na mojej liście, brzmi: „Znajdowanie struktury losowo: algorytmy stochastyczne do konstruowania przybliżonych rozkładów macierzy” Halko i in.
gappy
4

Dla NNMF Lee i Seung opisują iteracyjny algorytm, który jest bardzo prosty do wdrożenia. W rzeczywistości dają dwa podobne algorytmy, jeden do minimalizacji normy resztkowej Frobeniusa, drugi do minimalizacji Rozbieżności Kullbacka-Leiblera aproksymacji i macierzy oryginalnej.

shabbychef
źródło
3

Może znajdziesz interesujące

  1. [Learning with Matrix Factorizations] Praca doktorska Nathana Srebro,
  2. [Badanie różnych metod faktoryzacji macierzy dla dużych systemów rekomendujących] , Gábor Takács i in. i prawie taka sama technika opisana tutaj

Dwa ostatnie łącza pokazują, w jaki sposób rzadkie faktoryzacje macierzy są używane w filtrowaniu grupowym. Uważam jednak, że algorytmy faktoryzacji podobne do SGD mogą być przydatne gdzie indziej (przynajmniej są wyjątkowo łatwe do kodowania)

bijey
źródło
2

Witten, Tibshirani - Karany rozkład macierzy

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

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

Martinsson, Rokhlin, Szlam, Tygert - Randomized SVD

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

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

pslice
źródło
5
Dzięki. Znam oba artykuły. Nie jestem wielkim fanem Witten [nie Whitten] i wsp., Ponieważ myślę, że są ważniejsze prace na temat rzadkich rozkładów. W przypadku randomizowanego SVD szczególnie podoba mi się artykuł przeglądowy „Znalezienie struktury z przypadkowością: algorytmy stochastyczne do konstruowania przybliżonych rozkładów macierzy” ( arxiv.org/abs/0909.4061 ) również współautorem Martinssona.
gappy
zgadzam się. Właśnie opublikowałem 2 artykuły, o których nikt nie wspominał.
pslice
2

Na tegorocznych targach NIPS ukazał się krótki artykuł na temat rozproszonego SVD na dużą skalę, który działa w jednym przejściu przez macierz przesyłania strumieniowego .

Dokument jest bardziej zorientowany na implementację, ale przedstawia rzeczy z perspektywy czasu rzeczywistego i zegara na ścianie. Tabela na początku jest również dobrą ankietą.

pisk
źródło
Co oznacza skrót NIPS?
onestop
Dodano link @onestop. NIPS = Neural Information Processing Systems. To jest społeczność (nie system :)). Ale pisk mówi o konferencji NIPS 2010.
Robin Girard