Aktualizacja rozkładu SVD po dodaniu jednego nowego wiersza do matrycy

Załóżmy, że mam gęstą macierz o , z rozkładem SVD W mogę obliczyć SVD w następujący sposób: . $\textbf{A}$ $m \times n$

A = {U S V}^{⊤} .

$\mathbf{A}=\mathbf{USV}^\top.$ Rsvd(A)

Jeśli nowy -ty wiersz zostanie dodany do , czy można obliczyć nowy rozkład SVD na podstawie starego (tj. Przy użyciu , i ), bez ponownego obliczania SVD od zera? $(m+1)$ $\mathbf A$ $\mathbf U$ $\mathbf S$ $\mathbf V$

algorithms svd linear-algebra matrix-decomposition numerics użytkownik 1436187
źródło

Sprawdź literaturę rank 1 updates. Szybkie wersje online SVD dla lekkich systemów rekomendujących marki to pierwszy dostępny dokument. Niestety nie widziałem czegoś dla SVD już zaimplementowanego w R. Aktualizacje Cholesky istnieją ( updownod Matrix) dzięki CHOLMOD. Rzadkość macierzy

naprawdę różni się od ostatecznego rozwiązania; zakładasz gęstą lub rzadką matrycę?

A

$A$

usεr11852 mówi Reinstate Monic

+1 do @ usεr11852. Należy również pamiętać, że aktualizacja kodów QR jest o wiele łatwiejsza i bardziej standardowa, aw niektórych aplikacjach QR jest wystarczające i nie trzeba tak naprawdę używać SVD. Pomyśl też o swojej aplikacji.

ameba mówi Przywróć Monikę

Tak, matryca jest gęsta.

user1436187

„Porzuć” literaturę polecającą i skup się na przetwarzaniu obrazu. Podobne pytania dotyczące wycieczek zostały zamieszczone w odniesieniu do „nowych zdjęć” w bazie danych. Na przykład moje przeczucie jest takie, że ktoś musi mieć algorytm, aby aktualizować wpisy swoich własnych interfejsów online. Ci faceci pracują z gęstymi reprezentacjami macierzy.

usεr11852 mówi Reinstate Monic

Niektóre powiązane wątki na innych stronach SE: scicomp.stackexchange.com/questions/2678 , scicomp.stackexchange.com/questions/19253 , mathoverflow.net/questions/143375 .

ameba mówi Przywróć Monikę

Tak, można zaktualizować rozkład SVD po dodaniu jednego nowego wiersza do istniejącej macierzy.

Zasadniczo to sformułowanie problemu „ dodaj jeden do ” jest znane jako aktualizacja rangi 1 . Link MathOverflow podany przez @amoeba na temat „ skutecznych aktualizacji rozkładu drugiej wartości rozkładu własnego ” jest doskonałym pierwszym krokiem, jeśli chcesz głębiej przyjrzeć się sprawie; pierwszy artykuł zawiera jednoznaczne rozwiązanie konkretnego pytania. Aby wyjaśnić, co oznaczają ranga pierwsza i ranga druga, nie należy się mylić, jeśli nowe jest takie, że: $A^*$

\begin{aligned} A^{*} = A - u v^{T} \end{aligned}

$\begin{align} A^* = A - uv^T \end{align}$

Gdzie i są wektorami, to nazywasz to aktualizacją pierwszego stopnia (lub zaburzeniem ). Podstawy tej aktualizacji są podyktowane formułą Shermana-Morrisona. . Jeśli zaburzenie jest więcej niż jedna ranga, tj. $u$ $v$

\begin{aligned} A^{*} = A - U V^{T} \end{aligned}

$\begin{align} A^* = A - UV^T \end{align}$

formuła Woodbury wchodzi w grę. Jeśli zobaczysz te formuły, zauważysz, że w grę wchodzi wiele odwrotności. Nie rozwiązujesz ich bezpośrednio. Ponieważ już rozwiązałeś już wiele z ich podsystemów (tzn. Masz już obliczony rozkład), wykorzystujesz je, aby uzyskać szybsze i / lub bardziej stabilne oszacowania. (Dlatego ludzie wciąż badają tę dziedzinę.) Użyłem książki „ Statystyka obliczeniowa ” JE Gentle'a jako odniesienia; Myślę, że rozdział. 5 Numeryczna algebra liniowa zapewni prawidłowe ustawienie. (Uber-klasyk: „ Matryca algebry z perspektywy statystyki ” Harville'a niestety nie dotyka aktualizacji rang.)

Patrząc na statystyki / aplikacje, aktualizacje pierwszego stopnia są powszechne w systemach rekomendujących, ponieważ można mieć tysiące wpisów klientów i ponownie obliczyć SVD (lub dowolny dekompozycję w tym zakresie) za każdym razem, gdy rejestruje się nowy użytkownik lub nowy produkt dodany lub usunięty jest dość marnotrawny (jeśli nie nieosiągalny). Zwykle matryce systemowe rekomendujące są rzadkie, co czyni algorytmy jeszcze bardziej wydajnymi. Dostępny pierwszy artykuł to „ Szybkie wersje SVD online dla lekkich systemów rekomendujących ” autorstwa M. Branda. Przechodząc do gęstych matryc, myślę, że patrząc na dokumenty z Rozpoznawania Wzorów i Przetwarzania Obrazowania, możesz daleko posunąć się do uzyskania właściwego algorytmu. Na przykład dokumenty:

Przyrostowe uczenie się dwukierunkowych głównych elementów do rozpoznawania twarzy (2009) przez Ren i Dai,
O stopniowym i niezawodnym uczeniu się podprzestrzeni (2003) Li i in.
Ekstrakcja sekwencyjna Karhunena-Loeve'a i jej zastosowanie do obrazów (2000) Levey i Lindenbaum.
Incremental Learning for Solid Solid Visual Tracking (2007) Ross i in.

wydaje się, że wszystkie zajmują się tym samym problemem w swoim rdzeniu; nadchodzą nowe funkcje i musimy odpowiednio szybko zaktualizować naszą reprezentację . Zauważ, że macierze te nie są symetryczne ani nawet kwadratowe. Inne dzieło M. Branda również może rozwiązać ten problem (patrz artykuł „ Szybkie modyfikacje niskiego rzędu cienkiego dekompozycji wartości pojedynczej (2006) ” - to również wspomniano w linku MO podanym na początku postu.) wiele świetnych prac na ten temat, ale większość z nich ma charakter mocno matematyczny (np. praca Benaych-Georgesa i Nadakuditi na temat „ wartości i wektorów niskiej rangi zaburzeń dużych prostokątnych macierzy losowych (2012)”) i nie sądzę, aby wkrótce pomogły w znalezieniu rozwiązania. Sugeruję, abyś skupił się na literaturze dotyczącej przetwarzania obrazu.

Niestety nie spotkałem się z żadnymi implementacjami R dla procedur aktualizacji 1. Odpowiedź na „ Aktualizowalną implementację SVD w Pythonie, C lub Fortranie? ” Z Computational Science SE zawiera szereg implementacji MATLAB i C ++, które warto rozważyć. Zwykle implementacje R, Python itp. Są opakowaniami wokół implementacji C, C ++ lub FORTRAN.

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

To miły komentarz, ale byłem rozczarowany, że nie znalazłem odpowiedzi na pytanie. Okazuje się, że inny artykuł Matthew Branda , powiązany z odpowiedzią MO, zawiera jednoznaczne rozwiązanie.

whuber

+1 zarówno Tobie, jak i @ Whuber (i nie sądzę, że należy unikać „powielania” jakichkolwiek informacji podanych na innej stronie SE! Argumentuję, że powinniśmy postarać się, aby informacje podane na tej stronie były samowystarczalne jak to możliwe. Rzeczywiście, prawie wszystkie informacje tutaj zawarte są w pewnym sensie powieleniem istniejących podręczników, zasobów internetowych lub artykułów naukowych). Jedno pytanie: wspomniałeś formuły Shermana-Morrisona i Woodbury'ego, które opisują, jak zmienia się odwrotność macierzy po aktualizacji rangi 1 lub wyższej rangi; co mają wspólnego z SVD?

ameba mówi Przywróć Monikę

Rozumiem, dlaczego możesz chcieć przekierowywać ludzi na strony MO dla tego linku, ale możesz rozważyć bezpośrednie stwierdzenie, że to rozwiązuje problem! („Dobry pierwszy krok” jest ogromnym niedopowiedzeniem.) Znaczna część Twojego komentarza może być źle zrozumiana jako wskazująca, że nie znalazłeś jeszcze dobrego rozwiązania.

whuber

@whuber: „Dobry” stał się „świetny”, a teraz wspomniałem też o gazecie, lepiej? :) (

Nawiasem mówiąc,

Ze względów historycznych: Bunch i Nielsen jako pierwsi zaprezentowali sposób aktualizacji i aktualizacji SVD. Metoda marki uogólnia metody tego starszego papieru.

JM nie jest statystykiem

Aktualizacja rozkładu SVD po dodaniu jednego nowego wiersza do matrycy

Odpowiedzi: