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:B ( n + m ) × ( n + m ) A = ( 0 B B ⊤ 0 ) . Algorytm obcinane SVD ≈ iteracyjny algorytm eigendecomposition .n × mb( n + m ) × ( n + m )
A = ( 0b⊤b0) .
Algorytm obcinane SVD ≈ iteracyjny algorytm eigendecomposition .
Najprostszy iteracyjny algorytm nazywa się iteracją mocy i jest rzeczywiście bardzo prosty:
- Zainicjuj random .x
- Aktualizacja .x ← A x
- Normalizuj.x ← x / ∥ 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:
- Golub i Van Loan, Obliczenia macierzowe
- Trefethen & Bau, Numeryczna algebra liniowa
- Demmel, stosowana numeryczna algebra liniowa
- Saad, Metody numeryczne dla dużych problemów z wartością własną
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: svd
wykonuje pełny rozkład za pomocą LAPACK i svds
oblicza określoną liczbę pojedynczych wektorów za pomocą ARPACK i jest to właściwie tylko opakowanie dla eigs
wywoł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.A A BbZAZAbZA
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ć.