Nagyon tág értelemben két megközelítés létezik a sajátérték vagy az egyes értékek lebontásának kiszámításához. Az egyik megközelítés a mátrix átlósítása, és ez lényegében a teljes sajátérték / egyesérték-bontást (a teljes sajátérték-spektrumot) eredményezi egyidejűleg, itt olvashat néhány áttekintést: Melyek a hatékony algoritmusok az egyesérték-bomlás (SVD) kiszámításához? Alternatív megoldásként olyan iteratív algoritmust használhat, amely egyszerre egy (vagy több) sajátvektort eredményez. Az iterációk a kívánt számú sajátvektor kiszámítása után leállíthatók.

Nem hiszem, hogy léteznének iteratív algoritmusok kifejezetten az SVD számára. Ennek az az oka, hogy kiszámítható egy $ n \ szorzat m $ mátrix SVD értéke $ \ mathbf B $ egy négyzet szimmetrikus $ (n + m) \ szorzat (n + m) $ mátrix eigendakompozíciójával $ mátrix $$ \ mathbf A = \ left (\ begin {array} {cc} 0 & \ mathbf B \\\ mathbf B ^ \ top & 0 \ end {array} \ right). $$ azt kérdezi, hogy milyen iteratív algoritmusok számolják az eigendekompozíciót: $$ \ text {algoritmus csonka SVD-hez} \ kb \ text {iteratív algoritmus eigendecompositionhoz. a> és valóban nagyon egyszerű:

1. Inicializálja a véletlenszerű $ \ mathbf x $ értéket.
2. Frissítse a $ \ mathbf x \ get \ mathbf A \ mathbf x $ értéket.
3. Normalizálja a $ \ mathbf x \ get \ mathbf x / \ | \ mathbf x \ | $ értékeket.
4. Ugrás a 2. lépésre, hacsak nem konvergál.

A bonyolultabb algoritmusok végső soron a teljesítmény iterációs ötleten alapulnak, de meglehetősen kifinomultak. A szükséges matematikát a Krylov alterek adják meg. Az algoritmusok Arnoldi iterációja (négyzet alakú nem szimmetrikus mátrixok esetén), Lanczos iteráció (négyzet alakú szimmetrikus mátrixok esetében), és ezek variációi, például pl. "implicit módon újraindította a Lanczos-módszert" és mi más.

Ezt megtalálhatja pl. a következő tankönyvek:

1. Golub & Van Loan, Matrix Computations
2. Trefethen & Bau, numerikus lineáris algebra
3. Demmel, alkalmazott numerikus lineáris algebra
4. Saad, numerikus Módszerek nagy sajátérték-problémákra

Minden ésszerű programozási nyelv és statisztikai csomag (Matlab, R, Python numpy, Ön megnevezi) ugyanazokat a Fortran könyvtárakat használja saját / egyes értékbontások. Ezek a LAPACK és az ARPACK. Az ARPACK az ARnoldi PACKage rövidítését jelenti, és az Arnoldi / Lanczos iterációkról szól. Például. a Matlab-ban két funkció létezik az SVD számára: az svd teljes lebontást hajt végre a LAPACK-on keresztül, az svds pedig az ARPACK-on keresztül kiszámít egy adott számú egyes vektorot, és valójában csak egy eigs hívás a "négyzet alakú" mátrixon.

Frissítés

Kiderült, hogy a Lanczos algoritmusnak vannak olyan változatai, amelyek kifejezetten a $ \ mathbf B $ téglalap alakú mátrix SVD-jének végrehajtására szabva, anélkül, hogy először egy $ \ mathbf A $ négyzetmátrixot készítettünk volna. A központi kifejezés itt a Lanczos bidiagonalization ; amennyire megértem, lényegében trükk, hogy a $ \ mathbf A $ Lanczos-iterációinak minden lépését közvetlenül a $ \ mathbf B $ -on hajtjuk végre anélkül, hogy valaha is elkészítenénk a $ \ mathbf A $ -ot, és ezzel helyet és időt spórolnánk.

Van egy Fortran könyvtár ezekre a módszerekre is, az úgynevezett PROPACK:

A PROPACK szoftvercsomag funkciókat tartalmaz az egyes értékek felbontásának kiszámításához. nagy és ritka vagy strukturált mátrixok. Az SVD rutinok a Lanczos bidiagonalization algoritmuson alapulnak, részleges reortogonalizációval (BPRO).

Úgy tűnik azonban, hogy a PROPACK sokkal kevésbé szabványos, mint az ARPACK, és a normál programozási nyelvek nem támogatják natív módon. Rasmus Larsen írta, akinek nagy, 90 oldalas, 1998-as Lanczos bidiagonalization részleges reortogonalizációval című tanulmánya látszik jó áttekintéssel. Köszönet @MichaelGrant-nek ezen a Computational Science SE szálon keresztül.

A legújabb cikkek közül a legnépszerűbbnek tűnik Baglama & Reichel, 2005, Augmented implicit módon újraindította Lanczos-t. bidiagonalizációs módszerek, amelyek valószínűleg a legkorszerűbbek. Köszönet @Dougal-nak, hogy megadta ezt a linket a megjegyzésekben.

2. frissítés

Valójában egy teljesen más megközelítés létezik, amelyet az áttekintő cikk részletesen leír. magadra hivatkoztál: Halko et al. 2009, Struktúra keresése véletlenszerűséggel: Valószínűségi algoritmusok hozzávetőleges mátrixbontások felépítéséhez. Nem tudok róla annyit, hogy kommentelhessek.

Most találtam rá a szálra a gyors SVD-k segítségével, ezért megpróbálom magam kitalálni, de talán érdemes megvizsgálni az adaptive cross approximation (ACA) elemet.

Nem igazán tudom, hogy milyen a probléma, vagy mire van szükséged, de ha a mátrixod $ M $ sima függvényekből van kiszámítva, és csak egy hozzávetőleges elkülönített reprezentáció $ M = \ sum_ {i = 0} ^ k U_i \ cdot V ^ T_i $ , és valójában nem egy "megfelelő" SVD, az ACA algoritmus rendelkezik (majdnem ) lineáris számítási komplexitás ( $ N \ szor N $ mátrix, akkor majdnem $ O (N) $ ). Tehát nagyon gyors; sajnos sokan könnyedén használják a "gyors" szót.

Ismét a problémájától függ, hogy ez működik-e. Sok esetben személyesen találkozom, az ACA nagyon hasznos numerikus eszköz.

Note: ezt meg akartam írni kommentként, de mivel most hoztam létre ezt a fiókot, nincs elég hírem a megjegyzésekhez ... De a közzététel működik.

Itt van egy technika, amelyet korábban sikeresen alkalmaztam egy csonka SVD kiszámításához (a Netflix adatkészleten). ebből a cikkből származik. Együttműködő szűrési beállításnál meg kell jegyeznem, hogy az értékek nagy része hiányzik, és a lényeg az, hogy előre jelezzük őket , ezért ha csonka SVD-t használ egy ilyen probléma megoldására, akkor olyan technikát kell használnia, amely ilyen körülmények között működik. Rövid leírás:

1. Mielőtt bármit megtenne, illesszen be egy egyszerű modellt (pl. Globális átlag + oszlop és sor konstans értékek), és csak ezt követően tegye át a csonka használatát SVD, hogy illeszkedjen a maradványokhoz.
2. Inicializáljon egy k hosszúságú véletlenszerű vektort (ahol ez a rang, amire csonkol) minden sorba és oszlopba (a Netflix esetében minden filmhez és felhasználóhoz).
3. Tartsa rögzítve a sorvektort, és frissítse az oszlopvektort, hogy minimalizálja a hibát az ismert bejegyzések a mátrixban. Az eljárás matlab kódban van megadva a cikkben.
4. Tartsa rögzítve az oszlopvektort, és frissítse a sorvektorokat analóg módon.
5. Ismételje meg a 3 & 4-et, amíg össze nem ér, vagy nem kap elég jó eredmények.