Jaki jest obecny stan wiedzy w zakresie algorytmów dekompozycji liczby pojedynczej?

12

Pracuję nad biblioteką macierzy zawierającą tylko nagłówki, aby zapewnić pewien rozsądny stopień możliwości algebry liniowej w tak prostym pakiecie, jak to możliwe, i próbuję zbadać, jaki jest obecny stan techniki: obliczanie SVD złożona macierz.

Robię dwufazowy rozkład, dwukieragonalizację, a następnie obliczanie wartości osobliwych. W tej chwili używam metody gospodarstwa domowego do bidiagonalizacji (uważam, że LAPACK również tego używa) i myślę, że jest to tak dobre, jak to możliwe obecnie (chyba że ktoś wie o algorytmie dla tego..). O(N2)

Obliczenie liczby pojedynczej jest następne na mojej liście i jestem nieco poza pętlą, jakie są wspólne algorytmy do tego celu. Przeczytałem tutaj, że badania zmierzają w kierunku metody iteracji odwrotnej, która gwarantuje ortogonalność ze złożonością . Chciałbym usłyszeć o tym lub innych postępach.O(N)

linear-algebra matrix svd gct
źródło
czy istnieje dokumentacja dla biblioteki macierzy zawierającej tylko nagłówki (oprócz .h)? Dodaj także tag „svd”.
denis

Odpowiedzi:

7

„Randomizowane algorytmy” stały się ostatnio dość popularne w przypadku częściowych dysków DVD. Implementację zawierającą tylko nagłówek można pobrać tutaj: http://code.google.com/p/redsvd/

Przegląd aktualnych metod można znaleźć tutaj: http://arxiv.org/abs/0909.4061

W przypadku pełnych płyt DVD nie jestem pewien, czy możesz zrobić lepiej niż Domownik.

dranxo
źródło
Brzmi bardzo interesująco, muszę rzucić okiem na ten artykuł, dzięki!
gct
OP interesuje się algorytmami dla gęstych matryc. Nie sądzę, aby algorytmy losowe były konkurencyjne w tym środowisku, jeśli w ogóle działają.
Federico Poloni
Ten post wskazał, że metody losowe działają dobrze na gęstych matrycach research.facebook.com/blog/294071574113354/fast-randomized-svd
dranxo
@dranxo Nie ma żadnych porównań dokładności w tym poście, a wyniki pomiaru czasu nie wyglądają zbyt drobiazgowo. Ponadto algorytmy randomizowane opierają się na projekcji + dokładnym rozwiązaniu problemu na małą skalę. Oznacza to, że OP i tak wymagałoby wdrożenia „standardowej metody” dla wynikającego z tego problemu na małą skalę.
Federico Poloni
Słusznie. Chociaż jestem trochę zdezorientowany, dlaczego powinniśmy myśleć, że te metody działają tylko na rzadkich matrycach. Bezpośrednio z streszczenia artykułu Joela Troppa: „W przypadku gęstej macierzy wejściowej algorytmy losowe wymagają operacji zmiennoprzecinkowych (flop) O (mn log (k)) w przeciwieństwie do O (mnk) dla klasycznych algorytmów”. arxiv.org/pdf/0909.4061v2.pdf
dranxo
4

Przeczytałem tutaj, że badania zmierzają w kierunku metody iteracji odwrotnej, która gwarantuje ortogonalność ze złożonością . Chciałbym usłyszeć o tym lub innych postępach.O(N)

(Chciałem tylko zrobić kilka komentarzy, ponieważ nie mam czasu na opisywanie szczegółów, ale stało się dość duże jak na pole komentarza).

Wierzę, że byłby to algorytm MRRR (wiele stosunkowo solidnych reprezentacji) Dhillona i Parletta. Jest to zakorzenione w poprzedniej pracy Fernando, która z kolei została zainspirowana problemem postawionym przez Jima Wilkinsona w jego monumentalnej książce na temat problemów z wartością własną. Część „iteracji odwrotnej” do uzyskiwania pojedynczych wektorów jest zakorzeniona w koncepcji „skręconych faktoryzacji” Fernando , które wykorzystują macierze faktoringu do i dekompozycje.U D U ⊤LDL⊤UDU⊤

Z drugiej strony część algorytmu „wartość osobliwa” pochodzi z algorytmu (przesuniętej) różniczkowej różnicy ilorazu (dqd (s)) , który jest zwieńczeniem wcześniejszych prac Fernando, Parletta , Demmela i Kahana (z inspiracją od Heinza Rutishausera).

Jak zapewne wiesz, metody SVD zwykle rozpoczynają się od rozkładu dwukierunkowego najpierw, zanim zostaną uzyskane wartości osobliwe z macierzy dwukierunkowej. Niestety, nie jestem zbytnio poinformowany o aktualnej najlepszej metodzie dwukierunkowego rozkładu frontonu; ostatnio sprawdziłem, zwykłą metodą jest rozpoczęcie od rozkładu QR z obrotową kolumną, a następnie zastosowanie przekształceń ortogonalnych odpowiednio do współczynnika trójkątnego, aby w końcu uzyskać rozkład dwukierunkowy.

Rozumiem, że byłem skąpy w szczegółach; Spróbuję uściślić tę odpowiedź, gdy będę mieć dostęp do mojej biblioteki ...

JM
źródło
Matryca do postaci dwu-przekątnej, zrób kolumnę, a następnie rząd, powtórz w dół po przekątnej: użyj gestów lub gospodarstwa domowego, aby wyzerować kolumnę do przekątnej, a następnie zrób to samo dla rzędu do super-przekątnej.
adam W
Zignoruj ​​mój poprzedni komentarz, myślałem o formie trójstronnej. Przepraszam. Bi-diagonalizacja nie jest trywialna w podobieństwie (faktycznie ujawniłaby wartości własne), ale twoje odniesienie nie robi podobieństwa, robi coś innego; lewy i prawy pomnóż przez różne macierze ortogonalne. jest dwu-przekątna z i , co można zrobić tak, jak mówisz najpierw z QR, ale nie tak łatwo opisać w komentarzu. Mógłbym być zainteresowany, gdybyś uściślił odpowiedź dalej (ale mógłbym również ją rozgryźć, ponieważ moje studia zmierzają obecnie w tym kierunku). U U ⊤ = I V V ⊤ = IUAVUU⊤=IVV⊤=I
adam W