Jakie są szybkie algorytmy obliczania skróconego SVD?

Ewentualnie od tematu tutaj, ale istnieje kilka ( jeden , dwa ) pytania związane już.

Grzebanie w literaturze (lub wyszukiwanie google za pomocą Skróconych algorytmów SVD) ujawnia wiele artykułów, które wykorzystują obcięte SVD na różne sposoby i twierdzą (frustrujące, często bez cytowania), że istnieją szybkie algorytmy do ich obliczania, ale nikt nie wydaje się wskazywać na te algorytmy.

Jedyne, co mogę znaleźć, to pojedynczy randomizowany algorytm wykorzystywany w bibliotece redSVD .

Chciałbym zobaczyć zestaw dokładnych i niedokładnych algorytmów, odpowiednich do zrozumienia, jak działają systemy (ale niekoniecznie do ich faktycznego wdrożenia!).

Czy ktoś ma dobre referencje do tego rodzaju rzeczy?

algorithms svd numerics John Doucette
źródło

Jeśli chcę dobrze przechowywać dane, używam b-drzewa (lub rb-drzewa) w haszu (pomyśl o ram). Gdybym miał b-drzewo dla danych, to mógłbym w O (log (n)) próbkować kwantyle czasu i tym podobne. Założę się, że przy dużych danych takie próbkowanie może być wykorzystane do obliczenia przyzwoitego rzadkiego przybliżenia macierzy svd w krótkim czasie. Możesz także wyszukać „wykrywanie skompresowane”, które jest bardzo statystycznym podejściem do ekstremalnej kompresji danych.

EngrStudent - Przywróć Monikę

Przez obcięte SVD masz na myśli, że jesteś zainteresowany znalezieniem tylko kilku wiodących pojedynczych wektorów / wartości, a nie wszystkich?

ameba mówi Przywróć Monikę

@amoeba Tak, taki jest pomysł.

John Doucette,

Odpowiedzi:

Mówiąc bardzo ogólnie, istnieją dwa podejścia do obliczania wartości własnych lub rozkładów wartości pojedynczych. Jednym z podejść jest diagonalizacja macierzy, która zasadniczo daje cały rozkład wartości własnej / liczby pojedynczej (całe spektrum wartości własnych) w tym samym czasie, patrz przegląd tutaj: Jakie są wydajne algorytmy do obliczania rozkładu wartości pojedynczej (SVD)? Alternatywą jest użycie algorytmu iteracyjnego, który daje jeden (lub kilka) wektorów własnych na raz. Iteracje można zatrzymać po obliczeniu żądanej liczby wektorów własnych.

Nie sądzę, że istnieją algorytmy iteracyjne specjalnie dla SVD. Wynika to z faktu, że można obliczyć SVD macierzy macierzy , wykonując składnię złożoną z kwadratowej symetrycznej macierzyDlatego zamiast pytać, jakie algorytmy obliczają obcięty SVD, powinieneś zapytać, jakie algorytmy iteracyjne obliczają eigendecomposition: $n\times m$ $\mathbf B$ $(n+m)\times(n+m)$

ZA = (\begin{array}{cc} 0 & b \\ b^{⊤} & 0 \end{array}) .

$\mathbf A=\left(\begin{array}{cc}0 & \mathbf B\\\mathbf B^\top & 0\end{array}\right).$

algorytm skróconego SVD \approx algorytm iteracyjny dla składu eigend .

$\text{algorithm for truncated SVD} \approx \text{iterative algorithm for eigendecomposition}.$

Najprostszy iteracyjny algorytm nazywa się iteracją mocy i jest rzeczywiście bardzo prosty:

Zainicjuj random . $\mathbf x$
Aktualizacja . $\mathbf x \gets \mathbf A\mathbf x$
Normalizuj. $\mathbf x \gets \mathbf x / \|\mathbf x\|$
Idź do kroku 2, chyba że są zbieżne.

Wszystkie bardziej złożone algorytmy są ostatecznie oparte na pomyśle iteracji mocy, ale stają się dość wyrafinowane. Niezbędną matematykę zapewniają podprzestrzenie Kryłowa . Algorytmy to iteracja Arnoldiego (dla kwadratowych macierzy niesymetrycznych), iteracja Lanczosa (dla kwadratowych macierzy symetrycznych) i ich odmiany, takie jak np. „Niejawnie zrestartowana metoda Lanczosa” i tak dalej.

Można to znaleźć np. W następujących podręcznikach:

Wszystkie rozsądne języki programowania i pakiety statystyczne (Matlab, R, Python numpy, jak go nazywacie) używają tych samych bibliotek Fortran do przeprowadzania rozkładów wartości własnych / liczby pojedynczej. Są to LAPACK i ARPACK . ARPACK to skrót od ARnoldi PACKage, a wszystko dotyczy iteracji Arnoldi / Lanczos. Np. W Matlabie istnieją dwie funkcje SVD: svdwykonuje pełny rozkład za pomocą LAPACK i svdsoblicza określoną liczbę pojedynczych wektorów za pomocą ARPACK i jest to właściwie tylko opakowanie dla eigswywołania na macierzy „kwadratowej”.

Aktualizacja

Okazuje się, że warianty algorytmu lanczos które są specjalnie dostosowane do wykonywania SVD prostokątnej matrycy bez wyraźnego skonstruowanie macierzy kwadratowej pierwszego. Centralnym terminem jest tutaj dwukieragonalizacja Lanczosa ; o ile rozumiem, jest zasadniczo sztuczka, aby wykonać wszystkie kroki iteracji Lanczosa na bezpośrednio na nigdy nie budując a tym samym oszczędzając miejsce i czas. $\mathbf B$ $\mathbf A$ $\mathbf A$ $\mathbf B$ $\mathbf A$

Istnieje również biblioteka Fortran dla tych metod, nazywa się PROPACK :

Pakiet oprogramowania PROPACK zawiera zestaw funkcji do obliczania rozkładu wartości pojedynczych dużych i rzadkich lub strukturalnych macierzy. Procedury SVD są oparte na algorytmie bidiagonalizacji Lanczos z częściową reorthogonalizacją (BPRO).

Jednak PROPACK wydaje się być znacznie mniej standardowy niż ARPACK i nie jest natywnie obsługiwany w standardowych językach programowania. Jest napisany przez Rasmus Larsen, który ma dużą 90-stronicową gazetę Lanczos o długości 90 stron z 1998 r. Z częściową reortogonalizacją, co wydaje się dobrym przeglądem. Dzięki @MichaelGrant za pośrednictwem tego wątku Computational Science SE .

Wśród najnowszych prac najpopularniejszą wydaje się być Baglama i Reichel, 2005, Augmented domyślnie wznowił metody bidiagonalizacji Lanczosa , które prawdopodobnie są na zaawansowanym poziomie. Dzięki @Dougal za podanie tego linku w komentarzach.

Aktualizacja 2

Rzeczywiście istnieje zupełnie inne podejście opisane szczegółowo w artykule przeglądowym, który sam zacytowałeś: Halko i in. 2009, Znajdowanie struktury z przypadkowością: Probabilistyczne algorytmy do konstruowania przybliżonych rozkładów macierzy . Nie wiem o tym wystarczająco dużo, aby komentować.

ameba mówi Przywróć Monikę
źródło

Zauważ, że istnieją metody iteracji specyficzne dla SVD; np. Augmented Implicitly Restarted Lanczos Bidiagonalization Methods , J. Baglama i L. Reichel, SIAM J. Sci. Comput. 2005. (Nie czytałem gazety, aby dowiedzieć się, czy zasadniczo różni się ona od podejścia własnego, które podałeś, po prostu wiedz, że ludzie lubią tę metodę.)

Dougal

Dzięki za link, @Dougal. Powinienem powiedzieć, że tak naprawdę nie znam żadnej z tych metod, więc nie mogę tego komentować. Byłoby wspaniale, gdyby ktoś bardziej kompetentny wyjaśniłby związek między różnymi metodami iteracyjnymi. O ile rozumiem, waniliowa metoda Lanczosa służy do obliczania wartości własnych macierzy kwadratowej, a nie SVD; „Wzmocniony niejawnie zrestartowany Lanczos” powinien być z nim ściśle powiązany, ale masz rację - wydaje się, że dotyczy bezpośrednio SVD. Nie jestem pewien, jak to wszystko pasuje do siebie. Zaktualizuję swoją odpowiedź, jeśli kiedykolwiek przyjrzę się jej bliżej.

ameba mówi Przywróć Monikę

@Dougal, zrobiłem pobieżną lekturę i dokonałem aktualizacji.

ameba mówi Przywróć Monikę

@amoeba „obciąłby SVD” w kontekście regularnych najmniejszych kwadratów zasadniczo byłby taki sam jak „regresja podstawowych składników” ?

GeoMatt22,

@amoeba Czy możesz skomentować losową implementację SVD na Facebooku , niektórzy ludzie twierdzą , że jest to obecnie jedno z najszybszych możliwych rozwiązań. Byłoby wspaniale, gdybyś mógł edytować i komentować również na ten temat.

Tim

Właśnie natknąłem się na wątek za pomocą szybkich plików SVD googlujących, więc staram się sam coś wymyślić, ale może powinieneś przyjrzeć się adaptacyjnemu przybliżeniu krzyżowemu (ACA).

$M$ $M=\sum_{i=0}^k U_i\cdot V^T_i$ $N\times N$ $O(N)$

Znowu zależy to od twojego problemu, czy to zadziała. W wielu przypadkach, z którymi osobiście się spotykam, ACA jest bardzo przydatnym narzędziem numerycznym.

Uwaga: chciałem napisać to jako komentarz, ale ponieważ właśnie utworzyłem to konto, nie mam wystarczającej reputacji do komentowania ... Ale publikowanie działa.

oli
źródło

Oto technika, którą w przeszłości z powodzeniem stosowałem do obliczania obciętego SVD (w zestawie danych Netflix). Został zaczerpnięty z tego artykułu . W ustawieniu wspólnego filtrowania należy zauważyć, że brakuje większości wartości, a chodzi o to, aby je przewidzieć , więc aby użyć obciętego SVD do rozwiązania takiego problemu, należy zastosować technikę, która działa w tych warunkach. Krótki opis:

Zanim cokolwiek zrobisz, dopasuj prosty model (np. Średnia globalna + wartości stałych kolumn i wierszy) i tylko wtedy, gdy to zrobisz, powinieneś przejść do używania obciętego SVD w celu dopasowania reszt.
Zainicjuj losowy wektor długości k (gdzie jest to pozycja, którą przycinasz) do każdego wiersza i kolumny (do każdego filmu i użytkownika w przypadku Netflix).
Utrzymaj wektory wierszowe w pozycji stałej i zaktualizuj wektory kolumnowe, aby zminimalizować błąd wrt znane wpisy w macierzy. Procedura jest podana w kodzie matlab w artykule.
Unieruchom wektory kolumnowe i zaktualizuj wektory wierszowe w analogiczny sposób.
Powtarzaj 3 i 4, aż zbiegniesz się lub uzyskasz wystarczająco dobre wyniki.

Kikut Joe Pete
źródło