Jakie są wydajne algorytmy do obliczania dekompozycji wartości pojedynczej (SVD)?

Artykuł w Wikipedii na temat analizy głównych komponentów stwierdza, że

Istnieją wydajne algorytmy do obliczania SVD bez konieczności formowania macierzy , więc obliczanie SVD jest obecnie standardowym sposobem obliczania analizy głównych składników z macierzy danych, chyba że wymagana jest tylko garść składników. $X$ $X^TX$

Czy ktoś mógłby mi powiedzieć, o jakich skutecznych algorytmach mówi ten artykuł? Nie podano żadnego odniesienia (adres URL lub cytat do artykułu proponującego ten sposób obliczeń byłby miły).

— svd
źródło

Wyszukiwarka Google algorytmu dekompozycji pojedynczej wartości doskonale radzi sobie z wyróżnianiem odpowiednich informacji.

— whuber

Nie zapomnij usunąć średniej przed SVD dla PCA!

— Memming

Wypróbuj Lanczos SVD!

— ciri

Głównym koniem obliczeniowym przy obliczaniu SVD jest algorytm QR . Powiedziawszy, że istnieje wiele różnych algorytmów do obliczania rozkładu wartości w liczbie pojedynczej ogólnej macierzy -na- . Świetny schemat problemu dostępny tutaj (z dokumentacji MKL Intela ) jest następujący: $M$ $N$ $A$ wprowadź opis zdjęcia tutaj

Jak widać, w zależności od przypadku użycia istnieją różne podejścia (rutynowe konwencje nazewnictwa można znaleźć tutaj ). Jest tak, ponieważ na przykład istnieją formy matrycowe, w których redukcja Householdera może być droższa niż rotacja Givens (żeby wymienić dwa „oczywiste” sposoby uzyskania QR). Standardowym odniesieniem w tej sprawie są Matematyczne obliczenia Goluba i Van Loana (sugerowałbym użycie przynajmniej trzeciej edycji). Znalazłem też Å. Metody numeryczne Björcka dla problemów z najmniejszymi kwadratami bardzo dobre zasoby na ten temat; podczas gdy SVD nie jest głównym przedmiotem książki, pomaga kontekstualizować wykorzystanie go.

Jeśli muszę udzielić ci jednej ogólnej porady w tej sprawie , nie próbuj pisać własnych algorytmów SVD, chyba że pomyślnie ukończyłeś już kilka zajęć z Numerycznej Algebry Liniowej i wiesz, co robisz. Wiem, że zabrzmi to sprzecznie z intuicją, ale tak naprawdę jest to tona rzeczy, które mogą pójść nie tak, a ty kończysz (w najlepszym razie) nieoptymalne implementacje (jeśli nie są złe). Istnieje kilka bardzo dobrych darmowych pakietów w tej sprawie (np. Eigen , Armadillo i Trilinos, żeby wymienić tylko kilka.)

— usεr11852 mówi Reinstate Monic
źródło

X

$X$

A

$A$

M

$M$

N

$N$

A

$A$

X^{T} X

$X^TX$

Tak, myliłem się: QR nie ogranicza się do macierzy kwadratowych. Nawiasem mówiąc, +1. To pytanie było jednym z najczęściej głosowanych pytań bez odpowiedzi z tagiem pca , więc miło jest zobaczyć, że w końcu na nie odpowiedział.

— ameba mówi Przywróć Monikę

Twoja odpowiedź nie wymienia całej gamy algorytmów iteracyjnych. Czy to było celowe? Ktoś zadał pytanie o iteracyjne algorytmy SVD, zobacz Jakie są szybkie algorytmy obliczania skróconego SVD? , i zamieściłem tam odpowiedź, próbując przedstawić ogólny zarys. Być może powinniśmy przynajmniej połączyć nasze odpowiedzi. I na pewno byłoby wspaniale, gdybyś mógł rozwinąć swój dzięki dyskusji o algorytmach QR vs.

— ameba mówi Przywróć Monikę

Nie, to było przypadkowe. Odpowiedziałeś na swoje pytanie w swoim poście; Skrócone SVD są zasadniczo obciętymi składnikami głównymi (patrz na przykład ARPACK ). Istnieją pewne drobne różnice, ale są w porządku ; niektóre programy (np. MATLAB svds) posuwają się tak daleko, że po prostu używają ich skróconej funkcji SVD jako opakowania dla ich skróconych eigsprocedur eigendecomposition ( ).

— usεr11852 mówi: Przywróć Monic