Jak oblicza się SVD macierzy w praktyce

Jak na przykład MATLAB oblicza SVD danej macierzy? Zakładam, że odpowiedź prawdopodobnie obejmuje obliczenie wektorów własnych i wartości własnych A*A'. Jeśli tak jest, chciałbym również wiedzieć, jak to oblicza?

$AA^{T}$

Widzieć

GH Golub i C. Reinsch. Rozwiązania dotyczące pojedynczej wartości i rozwiązania najmniejszych kwadratów. Numerische Mathematik 14: 403-420, 1970.

Materiał ten jest omawiany w wielu podręcznikach dotyczących numerycznej algebry liniowej.

Oprócz (obecnie klasycznej) pracy Goluba-Reinscha Brian zauważa w swojej odpowiedzi (powiązałem ją z wersją podręcznika ), a także (także teraz klasycznej) poprzedniej pracy Goluba-Kahana , było wiele ważnych zmian w obliczeniach SVD od tego czasu. Najpierw muszę podsumować, jak działa zwykła metoda.

Idea obliczania SVD macierzy jest jakościowo podobna do metody stosowanej do obliczania składowej macierzy symetrycznej (i, jak zauważono w PO, istnieje między nimi ścisła zależność). W szczególności jeden przebiega w dwóch etapach: transformacja do macierzy dwu- kątnej , a następnie znalezienie SVD macierzy dwudzielnej. Jest to całkowicie analogiczne do procedury najpierw zredukowania macierzy symetrycznej do postaci tridiagonalnej, a następnie obliczenia składu eigend otrzymanego tridiagonalnego.

Jednym z najbardziej interesujących przełomów w obliczaniu SVD macierzy dwuwymiarowej był artykuł Jima Demmela i Velvela Kahana , który wykazał, że można z dużą dokładnością obliczyć nawet małe pojedyncze wartości macierzy dwuwymiarowej, odpowiednio modyfikując metodę początkowo zaproponowaną w Golub-Reinsch. Zostało to po przez (re?) Wykrywanie w DQD algorytmu , który jest potomkiem starego algorytmu iloraz różnicowego Rutishausera. (Beresford Parlett daje ładny dyskusji tutaj.) Jeśli pamięć służy, jest to obecnie preferowana metoda stosowana wewnętrznie przez LAPACK. Poza tym zawsze można było uzyskać wersje SVD rozwoju rozwiązań symetrycznych problemów własnych; na przykład istnieje wersja SVD typu „dziel i rządź”, a także wersja SVD starego algorytmu Jacobi (która może być dokładniejsza w niektórych okolicznościach).

Jeśli chodzi o bidiagonalizację, w dokumencie Barlowa nakreślono jedną ulepszoną metodę , która wymaga nieco więcej pracy niż oryginalna procedura Goluba i Reincsha, ale daje dokładniejsze macierze dwukierunkowe.