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

17

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.XXTX

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).

pca algorithms svd numerics svd
źródło
4
Wyszukiwarka Google algorytmu dekompozycji pojedynczej wartości doskonale radzi sobie z wyróżnianiem odpowiednich informacji.
whuber
1
Nie zapomnij usunąć średniej przed SVD dla PCA!
Memming
Wypróbuj Lanczos SVD!
ciri

Odpowiedzi:

12

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:MNAwprowadź 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
XA
1
MNAXTX
2
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