Uzupełnienie matrycy

Uzupełnienie macierzy częściowo ujawnionej macierzy 5 na 5 z rangą 1. Po lewej: obserwowana niekompletna macierz; Po prawej: wynik uzupełnienia macierzy.

Uzupełnianie macierzy to zadanie polegające na uzupełnieniu brakujących wpisów częściowo zaobserwowanej macierzy, co jest równoznaczne z imputacją danych w statystyce. Szeroka gama zestawów danych jest naturalnie zorganizowana w formie macierzowej. Jednym z przykładów jest macierz ocen filmów, jak pojawia się w problemie Netflix : Biorąc pod uwagę macierz ocen, w której każdy wpis reprezentuje ocenę filmu przez $}$$\ Displaystyle (i, j)$ klient ${\ displaystyle i}$ , jeśli klient $i}$$displaystyle$ obejrzał film jest poza tym nieobecny, chcielibyśmy przewidzieć pozostałe wpisy, aby dobrze zarekomendować klientom, co dalej oglądać. Innym przykładem jest macierz terminów dokumentu : Częstotliwości słów używanych w zbiorze dokumentów można przedstawić jako macierz, w której każdy wpis odpowiada liczbie wystąpień powiązanego terminu we wskazanym dokumencie.

Bez ograniczeń co do liczby stopni swobody w uzupełnionej macierzy problem ten jest niedookreślony , ponieważ ukrytym wpisom można by przypisać dowolne wartości. W związku z tym wymagamy pewnych założeń dotyczących macierzy, aby stworzyć dobrze postawiony problem , takich jak założenie, że ma ona wyznacznik maksymalny, jest dodatnio określona lub jest niskiego rzędu.

Na przykład można założyć, że macierz ma strukturę niskiego rzędu, a następnie szukać macierzy najniższego rzędu lub, jeśli znana jest ranga wypełnionej macierzy, macierzy rangi, która pasuje do znanych wpisów ${\ displaystyle r}$ . Ilustracja pokazuje, że częściowo ujawniona macierz rangi 1 (po lewej) może zostać uzupełniona zerowym błędem (po prawej), ponieważ wszystkie wiersze z brakującymi wpisami powinny być takie same jak w trzecim wierszu. W przypadku problemu z Netflixem oczekuje się, że macierz ocen będzie niskiej rangi, ponieważ preferencje użytkowników często można opisać kilkoma czynnikami, takimi jak gatunek filmu i czas premiery. Inne zastosowania obejmują widzenie komputerowe, w którym należy zrekonstruować brakujące piksele w obrazach, wykrywanie globalnego położenia czujników w sieci na podstawie częściowych informacji o odległości oraz nauka wieloklasowa . Problem uzupełniania macierzy jest na ogół NP-trudny , ale przy dodatkowych założeniach istnieją wydajne algorytmy, które osiągają dokładną rekonstrukcję z dużym prawdopodobieństwem.

Z punktu widzenia uczenia się statystycznego problem uzupełniania macierzy jest zastosowaniem regularyzacji macierzy , która jest uogólnieniem regularyzacji wektorowej . Na przykład w problemie uzupełniania macierzy niskiego rzędu można zastosować karę regularyzacyjną w postaci normy jądrowej ${\ Displaystyle R (X) = \ lambda \|X\|_ {*}}$

Uzupełnienie macierzy niskiego rzędu

Jednym z wariantów problemu uzupełniania macierzy jest znalezienie macierzy najniższego $,$ która pasuje $do$ macierzy , $.$ chcemy odzyskać, dla wszystkich wpisów w $}$ obserwowanych wpisów. Matematyczne sformułowanie tego problemu jest następujące:

${\ Displaystyle {\ rozpocząć {wyrównane} i {\ underset {X} {\ tekst {min}}} i {\ tekst { rank}}(X)\\&{\text{podlega}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}}$

Candès i Recht dowiedli, że przy założeniach dotyczących próbkowania obserwowanych wpisów i odpowiednio wielu próbkowanych wpisów problem ten ma unikalne rozwiązanie z dużym prawdopodobieństwem.

Równoważne sformułowanie, biorąc pod uwagę, że ${\ Displaystyle X_ {ij} = M_ {ij} \; \; \ dla wszystkich ja, j \ w mi$$,$$że$ macierz do odzyskania ma należy dla gdzie $jot$

Założenia

niedookreślony , często przyjmuje się szereg założeń dotyczących doboru próby obserwowanych wpisów i liczby wpisów objętych próbą .

Jednolite próbkowanie obserwowanych wpisów

Aby analiza była wykonalna, często zakłada się, że zbiór $obserwowanych$ wpisów i ustalonej liczności jest próbkowany losowo ze zbioru wszystkich podzbiorów wpisów o liczności ${\ Displaystyle | E |}$ . Aby jeszcze bardziej uprościć analizę, zamiast tego zakłada się, że $jest$ konstruowany przez $próbkowanie$ Bernoulliego , tj. że każdy wpis jest obserwowany . jeśli ${\ Displaystyle p}$ jest ustawiony na $N} {mn}}}$ { \ $Displaystyle {$$\ Frac$${$ gdzie jest oczekiwaną liczebnością i $\displaystyle m,\;n}$ to wymiary macierzy (niech ${\ displaystyle m <n}$ bez utraty ogólności), ${\ Displaystyle | E |}$ mieści się w granicach $dużym$ prawdopodobieństwem więc $próbkowanie$ Bernoulliego jest Innym uproszczeniem jest założenie, że wpisy są losowane niezależnie iz zastępstwem.

Dolna granica liczby obserwowanych wpisów

Załóżmy, że $<$$odzyskać$$), którą$ próbujemy , ma rangę { $}$$m$ . Istnieje dolna granica teoretycznej informacji, ile wpisów należy zaobserwować, zanim $zrekonstruować$ . Zestaw ${\ displaystyle m}$ przez ${\ displaystyle n}$$randze$ mniejszej lub równej ${\ Displaystyle (n + m) rr ^ {2}}$ rozmaitością algebraiczną w wymiarze ${\ Displaystyle {\ mathbb {C}} ^ {m \ razy n$ . $wyniku$ można pokazać, że co najmniej obserwowane w celu uzupełnienia ${\ Displaystyle {\ mathbb {C}} ^ {n \ razy n}}$ mieć unikalne rozwiązanie, gdy ${\ Displaystyle r \ równoważnik n/2}$ .

Po drugie, musi istnieć co najmniej jeden obserwowany wpis na wiersz i kolumnę ${\ displaystyle M}$ . Rozkład na wartości osobliwe $U \ Sigma V ^ {\ sztylet}}$ określony przez $Displaystyle$ . Jeśli wiersz $,$$nieobserwowany$ łatwo jest zobaczyć pojedynczy wektor $\ displaystyle M}$ , $displaystyle$$v_ {i}}$ , można zmienić na dowolną dowolną wartość i nadal uzyskać macierz pasującą zbioru obserwowanych wpisów. Podobnie, jeśli kolumna $displaystyle$ nieobserwowana, lewy pojedynczy wektor $M}$ , ${i}}$${\ displaystyle j ^ {\ tekst {th}}}$ może być dowolny. Jeśli założymy próbkowanie Bernoulliego zbioru obserwowanych wpisów, efekt kolekcjonera kuponów oznacza, że ​​​​należy przestrzegać wpisów rzędu ${\ Displaystyle O (n \ log n)},$ aby zapewnić obserwację z każdego wiersza i kolumny z dużym prawdopodobieństwem.

Łącząc niezbędne warunki i zakładając, że $)$ , dolna granica liczby obserwowanych wpisów wymaganych, aby zapobiec bycie niedookreślonym jest rzędu ${\ Displaystyle nr \ log n}$ .

Brak związku

Koncepcja niespójności powstała w skompresowanym wykrywaniu . Jest wprowadzany w kontekście uzupełniania macierzy, aby zapewnić, że wektory osobliwe $”$ w tym sensie, że wszystkie współrzędne każdego wektora osobliwego mają porównywalną wielkość, a nie tylko kilka współrzędnych o znacznie większym wielkości. Standardowe wektory bazowe są wtedy niepożądane jako wektory pojedyncze, a wektor matrix ${\ Displaystyle {\ Frac {1} {\ sqrt {n}}} {\ rozpocząć {bmatrix} 1 \\1 \\\ vdots \\1 \ koniec {bmatrix}}} w R n {\$ Displaystyle ${ R} ^{n}}$ jest pożądane. Jako przykład tego, co może pójść nie tak, jeśli pojedyncze wektory są wystarczająco „rzadkie”, rozważmy macierz $n$$1$ ⋯ $\ rozpocząć {bmatrix} 1 &$ with rozkład na wartości osobliwe ${\ Displaystyle I_ {m} {\ rozpocząć {bmatrix} 1 & 0 & \ cdots & 0 \\\ vdots &&\ vdots \\ 0&0&0&0 \ koniec {bmatrix}} I_ {n} }$ . Prawie $,$ wpisy muszą zostać pobrane zanim będzie można je zrekonstruować.

$Displaystyle$ Recht definiują spójność macierzy z kolumn i podprzestrzenią wymiarową $n}}$$\ mathbb {R} ^$$\ Displaystyle \ mu (U) = {\ Frac {n} {r}} \ max _ {i <n} \ | P_ {U} e_ {i }\|^{2}}$ jako , gdzie ${\ displaystyle P_ {U}} jest$ rzutem ortogonalnym na ${\ displaystyle U}$ . Niespójność następnie twierdzi, że biorąc pod uwagę $Displaystyle$$sztylet$ osobliwej macierzy , $}$$\ Sigma V ^ {$ U \ }

1. ${0}}$
2. Wpisy ${\ Displaystyle \ suma _ {k} u_ {k} v_ {k} ^ {\ sztylet}}$ mają wielkości górne ograniczone przez ${\ Displaystyle \ mu _ { 1} {\ sqrt {\ frac {r} {mn}}}}$

dla niektórych ${\ Displaystyle \ mu _ {0}, \; \ mu _ {1}}$ .

Uzupełnianie macierzy niskiego rzędu z szumem

W rzeczywistych aplikacjach często obserwuje się tylko kilka wpisów uszkodzonych przynajmniej przez niewielką ilość szumu. Na przykład w problemie z Netflixem oceny są niepewne. Candès i Plan wykazali, że możliwe jest uzupełnienie wielu brakujących wpisów dużych macierzy niskiego rzędu z zaledwie kilku zaszumionych próbek poprzez minimalizację norm jądrowych. Model hałaśliwy zakłada, że ​​obserwujemy

${\ Displaystyle Y_ {ij} = M_ {ij} + Z_ {ij}, (i, j) \ w \ Omega,}$

gdzie ${\ Displaystyle {Z_ {ij}: (i, j) \ in \ Omega}}$ jest terminem szumowym. Zauważ, że szum może być stochastyczny lub deterministyczny. Alternatywnie model można wyrazić jako

${\ Displaystyle P _ {\ Omega} (Y) = P _ {\ Omega} (M) + P _ {\ Omega} (Z)}$

gdzie jest $jot$ z wpisami dla $Z} \in \Omega}$${\ Displaystyle$$($ zakładając, że ${\ Displaystyle \| P_ {\ Omega} (Z) \|_ {F} \ równoważnik \ delta}$ dla pewnego ${\ displaystyle \ delta > 0}$ . Aby odzyskać niekompletną macierz, próbujemy rozwiązać następujący problem optymalizacyjny:

${\ Displaystyle {\ rozpocząć {wyrównane} i {\ underset {X} {\ tekst {min}}} & \ | X \ | _{*}\\&{\text{z zastrzeżeniem}}&\|P_{\Omega }(XY)\|_{F}\leq \delta \\\end{wyrównane}}}$

Spośród wszystkich macierzy zgodnych z danymi znajdź tę, która ma minimalną normę jądrową. Candès i Plan wykazali, że ta rekonstrukcja jest dokładna. Udowodnili oni, że gdy następuje idealne bezszumowe odzyskiwanie, wówczas uzupełnianie macierzy jest stabilne w stosunku do perturbacji. Błąd jest proporcjonalny do poziomu hałasu ${\ displaystyle \ delta}$ . Dlatego, gdy poziom szumu jest mały, błąd jest mały. Tutaj problem uzupełniania macierzy nie jest zgodny z ograniczoną właściwością izometrii (RIP). W przypadku macierzy RIP zakładałby, że operator próbkowania jest posłuszny

${\ Displaystyle (1-\ delta) \ | X \ | _ {F }^{2}\leq {\frac {1}{p}}\|P_{\Omega }(X)\|_{F}^{2}\leq (1+\delta )\|X\| _{F}^{2}}$

dla wszystkich macierzy $wystarczająco$$wystarczająco$ randze małej Sposoby mają również zastosowanie do problemów z odtwarzaniem rzadkich sygnałów, w których protokół RIP nie jest spełniony.

Uzupełnienie macierzy wysokiego rzędu

Ogólnie rzecz biorąc, uzupełnienie macierzy wysokiego rzędu jest NP-trudne . Jednak przy pewnych założeniach można uzupełnić pewną niekompletną macierz wysokiego rzędu lub nawet pełną macierz rang.

Eriksson, Balzano i Nowak rozważali problem uzupełniania macierzy przy założeniu, że kolumny macierzy należą do sumy wielu podprzestrzeni niskiego rzędu. Ponieważ kolumny należą do unii podprzestrzeni, problem może być postrzegany jako wersja problemu grupowania podprzestrzeni z brakującymi danymi . Niech $X}$$displaystyle$ będzie macierzą $,$ co najwyżej , z których każda ${\ displaystyle rank \ równoważnik r <n}$ i załóżmy, że ${\ Displaystyle N \ gg kn}$ . Eriksson, $Displaystyle CrN \ log ^ {2} (n)}$ i Nowak wykazali, że przy łagodnych założeniach każdą kolumnę można doskonale odzyskać z dużym prawdopodobieństwem z niekompletnej wersji, o ile przynajmniej do $R$ wpisy ${\ Displaystyle X}$ są obserwowane równomiernie losowo, ze stałą zależną od zwykłych warunków niespójności, geometrycznego układu podprzestrzeni i rozmieszczenia $podprzestrzeniach$

Algorytm obejmuje kilka kroków: (1) lokalne sąsiedztwa; (2) lokalne podprzestrzenie; (3) wyrafinowanie podprzestrzeni; (4) pełne uzupełnienie macierzy. Metodę tę można zastosować do uzupełniania macierzy odległości w Internecie i identyfikacji topologii.

Algorytmy wypełniania macierzy niskiego rzędu

Zaproponowano różne algorytmy uzupełniania macierzy. Obejmuje to algorytm oparty na relaksacji wypukłej, algorytm oparty na gradiencie i algorytm oparty na naprzemiennej minimalizacji.

Relaksacja wypukła

Problem minimalizacji rang jest NP-trudny . $zaproponowane$ przez Candèsa i Rechta, polega na utworzeniu wypukłej problemu i zminimalizowaniu normy która daje sumę osobliwych wartości ${\ Displaystyle M}$ ) zamiast ${\ Displaystyle {\ tekst {ranga}} (M)}$ która zlicza liczbę niezerowych wartości osobliwych M ${\ displaystyle M}$ ). Jest to analogiczne do minimalizowania normy L1- zamiast normy L0- dla wektorów. Relaksację wypukłą można rozwiązać za pomocą programowania półokreślonego (SDP), zauważając, że problem optymalizacji jest równoważny

${\ Displaystyle {\ rozpocząć {wyrównane} & {\ underset {W_ {1}, W_ {2}} {\ tekst {min}}} & & {\ tekst {ślad}} (W_ {1}) + {\ tekst {trace}}(W_{2})\\&{\text{podlega}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix }W_{1}&X\\X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{wyrównane}}}$

Złożoność użycia SDP do rozwiązania relaksacji wypukłej jest ${\ Displaystyle O ({\ text {max}} (m, n) ^ {4})}$ . Najnowocześniejsze solwery, takie jak SDPT3, mogą obsługiwać tylko macierze o rozmiarze do 100 na 100. Alternatywną metodą pierwszego rzędu, która w przybliżeniu rozwiązuje relaksację wypukłą, jest algorytm progowy wartości osobliwej wprowadzony przez Cai, Candès i Shen.

Candès i Recht pokazują, wykorzystując badanie zmiennych losowych w przestrzeniach Banacha , że ​​jeśli liczba obserwowanych wpisów jest rzędu max $\ displaystyle \ max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\ log n}$ (załóżmy bez utraty ogólności ${\ displaystyle m <n}$ ), problem minimalizacji rang ma unikalne rozwiązanie, które jest również rozwiązaniem jego wypukłej relaksacji z prawdopodobieństwem $1- {\ Frac {c} {n ^ {3}}}}$ Displaystyle stała do $\ displaystyle c}$ . Jeśli ranga $}$ ( ), rozmiar $M$ zbiór obserwacji redukuje się do rzędu ${\ Displaystyle \ mu _ {0} n ^ {1.2} r \ log n}$ . Wyniki te są prawie optymalne, ponieważ minimalna liczba wpisów, które należy zaobserwować, aby problem uzupełniania macierzy nie był niedookreślony, jest rzędu ${\ displaystyle nr \ log n}$ .

Wynik ten poprawili Candès i Tao. Osiągają granice różniące się od granic optymalnych jedynie polilogarytmicznymi poprzez wzmocnienie założeń. Zamiast właściwości niespójności przyjmują właściwość silnej niespójności z parametrem ${\ displaystyle \ mu _ {3}}$ . Właściwość ta stwierdza, że:

1. ${\ Displaystyle |\ langle e_ {a}, P_ {U} e_ {a'} \ rangle - {\ Frac {r} {m}} 1_ {a = a'} |\ równoważnik \ mu _ {3} {\ Frac {\ sqrt {r}} {m}}}$ za za $\ Displaystyle a, a'\ równoważnik m}$ i ${\ Displaystyle |\ langle e_ {b}, P_ {U} e_ {b '} \ rangle - {\ Frac {r} {n}} 1_ {b = b'} | \ równoważnik \ mu _ {3} {\ Frac {\ sqrt {r}} {n}}}$ dla ${\ Displaystyle b, b'\ równoważnik n}$
2. ∑ ${\ Displaystyle \ suma _ {i} u_ {i} v_ {i} ^ {\ sztylet}}$ ograniczone wielkością przez ${\ Displaystyle \ mu _ { 3}{\sqrt {\frac {r}{mn}}}}$

Intuicyjnie, silna niespójność macierzy stwierdza, że ​​​​ortogonalne rzuty standardowych wektorów bazowych na $rozmieszczone$ wielkości, które mają duże prawdopodobieństwo, gdyby pojedyncze wektory były $.$

${\ Displaystyle \ mu _ {3} ^ {4} n (\ log n) ^ {2}}$ gdy $\$$Displaystyle O (1)}$ , a liczba obserwowanych wpisów jest rzędu ( , problem minimalizacji rang ma unikalne rozwiązanie, które jest również rozwiązaniem jego wypukłej relaksacji z prawdopodobieństwem ${\ displaystyle 1-{\frac {c}{n^{3}}}}$ dla pewnej stałej ${\ displaystyle c}$ . Dla arbitralnego ${$ obserwowanych wpisów wystarczająca do spełnienia tego twierdzenia jest rzędu $\ Displaystyle \ mu _ {3} ^ {2} nr (\log n)^{6}}$

Innym podejściem do relaksacji wypukłej jest zminimalizowanie kwadratowej normy Frobeniusa przy ograniczeniu rangowym. Jest to równoważne rozwiązaniu

${\ Displaystyle {\ rozpocząć {wyrównane} & {\ underset {X} {\ tekst {min}}} && \ Vert X \ Vert _ {F} ^ {2} \\& {\ tekst {z zastrzeżeniem}} & & X_ {ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{Rank}}(X)\leq k.\end{aligned}}}$

Wprowadzając ortogonalną macierz projekcji $($ co oznacza ${\ Displaystyle Y ^ {2} = Y, Y = Y '}) w$ modelowania rangi ${\ Displaystyle X }$ przez ${\ Displaystyle X = YX, {\ tekst {ślad}} (Y) \ równoważnik k}$ i biorąc wypukłą relaksację tego problemu, otrzymujemy następujący program półokreślony

${\ Displaystyle {\ rozpocząć {wyrównane} & {\ underset {X, Y, \ teta} {\ tekst {min}}} & & {\ tekst {ślad}} (\ teta) \\& {\ tekst {z zastrzeżeniem }}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{ślad}}(Y)\leq k,0\preceq Y\preceq I\\&&& {\begin{pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}}$

Jeśli Y jest macierzą projekcji (tj. ma binarne wartości własne) w tej relaksacji, to relaksacja jest ciasna. W przeciwnym razie daje prawidłową dolną granicę ogólnego celu. Co więcej, można to przekształcić w wykonalne rozwiązanie z (nieco) większym celem poprzez chciwe zaokrąglenie wartości własnych Y. Co ciekawe, ta wypukła relaksacja może zostać rozwiązana przez naprzemienną minimalizację na X i Y bez rozwiązywania jakichkolwiek SDP, a zatem skaluje się poza typowe ograniczenia liczbowe najnowocześniejszych solwerów SDP, takich jak SDPT3 lub Mosek.

Podejście to jest szczególnym przypadkiem bardziej ogólnej techniki przeformułowania, którą można zastosować w celu uzyskania prawidłowej dolnej granicy dowolnego problemu niskiego rzędu, którego celem jest macierz-ślad-wypukłość.

Zejście gradientowe

i Oh rozważają wariant uzupełniania macierzy, w którym ranga macierzy $displaystyle m}$ która $ma$ zostać $m$ , jest $znana$ jako $styl wyświetlania r}$ . Zakładają próbkowanie wpisów przez Bernoulliego $M.$$współczynnik$ proporcji , ograniczoną wielkość wpisów ( górna granica ${\ Displaystyle M _ {\ tekst {max}}}$ ) i stały numer warunku ${\ Displaystyle {\ Frac {\ sigma _ {1}} {\ sigma _ {r}}}}$ (gdzie ${\ Displaystyle \ sigma _ {1}}$$)$$odpowiednio$ największymi najmniejszymi wartościami osobliwymi . Ponadto zakładają, że dwa warunki niespójności są spełnione przez μ $mu _ {0}}$${\ Displaystyle \ mu _ {1} {\ Frac {\ sigma _ {1}} {\ sigma _ {r}}}}$ gdzie ${\ Displaystyle \ mu _ {0}}$ i ${\ displaystyle \ mu _ {1}}$ są stałymi. Niech $do$ macierzą, która pasuje zbioru $gdzie$ i wynosi 0 $indziej$ Następnie proponują następujący algorytm:

1. Przytnij $,$ usuwając wszystkie obserwacje z kolumn o stopniu ${\ displaystyle {\ frac {2|E|}{n}}}$ ustawiając wpisy w kolumnach na 0. Podobnie usuń wszystkie obserwacje z wierszy o stopniu większym niż ${\ Displaystyle {\ Frac {2 | E |} {n}}}$ .
2. Projektuj na jego pierwsze główne składniki. $^ {E}}$$displaystyle$ . Wywołaj wynikową macierz ${\ Displaystyle {\ text {Tr}} (M ^ {E})}$ .
3. Rozwiąż ${\ Displaystyle \ min _ {X, Y} \ min _ {S \ w \ mathbb {R} ^ {r \ razy r}} {\ Frac {1} {2}} \ suma _ {i, j \ w E} (M_ {ij} - (XSY ^ {\ sztylet}) _ {ij}) ^ {2} + \ rho G (X, Y)} gdzie sol ( X , Y ) {$ \ $) )}$ to pewna funkcja regularyzacji przez opadanie gradientu z przeszukiwaniem linii . Zainicjuj ${\ Displaystyle X, \; Y}$ w ${\ Displaystyle X_ {0}, \; Y_ {0}}$ gdzie ${\ Displaystyle {\ tekst {Tr}} (M_ {E}) = X_ {0} S_ {0} Y_ {0} ^ {\ sztylet}}$ . Ustaw jako pewną funkcję zmuszającą $Y$${\ Displaystyle X, \;$ do $opadania$ jeśli $są$ .
4. Zwróć macierz ${\ Displaystyle XSY ^ {\ sztylet}}$ .

Kroki 1 i 2 algorytmu dają macierz ${\ Displaystyle {\ tekst {Tr}} (M ^ {E}$ zbliżoną do prawdziwej macierzy ( $mierzonej$ przez pierwiastek błędu średniokwadratowego (RMSE) ) z dużym prawdopodobieństwem. szczególności , $_$${\ Displaystyle {\ Frac {1} {mnM _ {\ tekst {max}} ^ {2}}} \| M - {\ tekst {Tr}} (M ^ {E}) \|_ {F} ^ {2} \ równoważnik C {\ frac {r} {m|E |}} {\ sqrt {\ frac {m} {n}}}}$ dla pewnej stałej do ${\ displaystyle C$ . ${\ Displaystyle \|\ cdot \|_ {F}} oznacza$ normę Frobeniusa . Należy zauważyć, że pełny zestaw założeń nie jest potrzebny do utrzymania tego wyniku. Warunek niespójności, na przykład, wchodzi w grę tylko w dokładnej rekonstrukcji. Wreszcie, chociaż przycinanie może wydawać się sprzeczne z intuicją, ponieważ obejmuje wyrzucanie informacji, zapewnia rzutowanie na jego pierwsze ${\ displaystyle$ składowe , co daje więcej informacji o podstawowej macierzy $M ^ {E$$} displaystyle M}$ niż o obserwowanych wpisach.

W kroku 3 przestrzeń macierzy kandydujących można zmniejszyć, zauważając, że problem wewnętrznej minimalizacji ma to samo rozwiązanie dla $(X, Y$$Y$ jak dla ${\ Displaystyle (XQ, YR)}$ gdzie ${\ Displaystyle Q}$$Displaystyle R}$ R $\$ są ortonormalne przez ${\ displaystyle r}$ . Następnie można wykonać zejście gradientowe nad iloczynem krzyżowym dwóch rozmaitości Grassmana . Jeśli ${\ Displaystyle r \ ll m, \; n}$ i obserwowany zestaw wpisów jest rzędu ${\ Displaystyle nr \ log n}$ , macierz zwrócona przez krok 3 jest dokładnie ${\ displaystyle M}$ . Wtedy algorytm jest optymalny pod względem rzędu, ponieważ wiemy, że aby problem uzupełniania macierzy nie był niedookreślony , liczba wpisów musi być rzędu ${\ displaystyle nr \ log n}$ .

Naprzemienna minimalizacja metodą najmniejszych kwadratów

Naprzemienna minimalizacja reprezentuje szeroko stosowane i empirycznie skuteczne podejście do znajdowania macierzy niskiego rzędu, które najlepiej pasują do danych. Na przykład w przypadku problemu uzupełniania macierzy niskiego rzędu ta metoda jest uważana za jedną z najdokładniejszych i najskuteczniejszych i stanowiła główny składnik zwycięskiej pracy w zadaniu Netflix. W podejściu naprzemiennej minimalizacji docelowa macierz niskiego rzędu jest zapisywana w postaci dwuliniowej :

${\ Displaystyle X = UV ^ {T}}$ ;

algorytm następnie na $znajduje$$najlepsze$ najlepsze . Chociaż ogólny problem nie jest wypukły, każdy podproblem jest zwykle wypukły i można go skutecznie rozwiązać. Jain, Netrapalli i Sanghavi dali jedną z pierwszych gwarancji wykonania naprzemiennej minimalizacji zarówno dla uzupełniania macierzy, jak i wykrywania macierzy.

Algorytm naprzemiennej minimalizacji można postrzegać jako przybliżony sposób rozwiązania następującego niewypukłego problemu:

${\ Displaystyle {\ rozpocząć {wyrównane} i {\ underset {U, V \ w \ mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega}(M)\|_{F}^{2} \\\koniec {wyrównany}}}$

Algorytm AltMinComplete zaproponowany przez Jain, Netrapalli i Sanghavi jest wymieniony tutaj:

1. Wejście : ${\ Displaystyle P _ {\ Omega} (M)$ zestaw , wartości $)$
2. Podział na podzbiory $2T + 1}$$Displaystyle$$, \ Omega _ {2T}}$ z każdym element należący do jednego z $Displaystyle$$\ Omega _ {t}}$ z równym prawdopodobieństwem (próbkowanie z zastępowaniem) Ω {\ Displaystyle \ Omega
3. ${\ Displaystyle {\ kapelusz {U}} ^ {0} = SVD ({\ Frac {1} {p}} P _ {\ Omega _ { 0}} (M), k )}$ tj. górne ${$ lewe wektory liczby pojedynczej $0}}(M)}$${\ Displaystyle {\ Frac {1} {p}} P _ {\ Omega _$
4. Przycinanie : $Displaystyle$ wszystkie elementy , które mają większą niż ${\ Frac {2 \ mu {\ sqrt {k}}} {\ sqrt {n}}}}$ do zera i ortonormalizujemy kolumny ${\ Displaystyle {\ hat {U}} ^ {0}}$
5. dla ${\ Displaystyle t = 0, \ cdots, T-1}$ zrobić
6. ${\ Displaystyle \ quad {\ kapelusz {V}} ^ {t + 1} \ lewostrzałka {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T }-M)\|_{F}^{2}}$
7. ${\ Displaystyle \ quad {\ kapelusz {U}} ^ {t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\razy k}}\|P_{\Omega _{T+t+1}}(U( {\kapelusz {V}}^{t+1})^{T}-M)\|_{F}^{2}}$
8. koniec dla
9. powrót ${\ Displaystyle X = {\ kapelusz {U}} ^ {T} ({\ kapelusz {V}} ^ {T}) ^ {T}}$

Pokazali to obserwując ${\ Displaystyle | \ Omega | = O (({\ Frac {\ sigma _ {1} ^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))}$ losowe wpisy niespójnej macierzy ${\ Displaystyle M}$$_$ może w $M$ _ Jeśli chodzi o złożoność próbki ( $, teoretycznie naprzemienna minimalizacja może$ większego $\ Omega}$ niż relaksacja wypukła. Jednak empirycznie wydaje się, że tak nie jest, co sugeruje, że granice złożoności próbki można jeszcze bardziej zawęzić. Pod względem złożoności czasowej pokazali, że AltMinComplete potrzebuje czasu

${\ Displaystyle O (| \ Omega | k ^ {2} \ log (1 / \ epsilon))}$ .

Warto zauważyć, że chociaż metody oparte na relaksacji wypukłej mają rygorystyczną analizę, algorytmy oparte na naprzemiennej minimalizacji są bardziej skuteczne w praktyce.

Aplikacje

Candès i Plan podsumowali kilka zastosowań uzupełniania macierzy w następujący sposób:

Filtrowanie zespołowe

Filtrowanie zespołowe polega na dokonywaniu automatycznych prognoz dotyczących zainteresowań użytkownika poprzez zbieranie informacji o gustach wielu użytkowników. Firmy takie jak Apple, Amazon, Barnes and Noble i Netflix próbują przewidzieć preferencje użytkowników na podstawie częściowej wiedzy. W tego rodzaju problemach z uzupełnianiem macierzy nieznana pełna macierz jest często uważana za niską, ponieważ tylko kilka czynników zazwyczaj wpływa na gusta lub preferencje jednostki.

Identyfikacja systemu

Mając kontrolę, chciałoby się dopasować liniowy, niezmienny w czasie model przestrzeni stanów w czasie dyskretnym

${\ Displaystyle {\ rozpocząć {wyrównane} x (t + 1) i =Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{wyrównane}}}$

$_ y(t)\in \mathbb {R} ^{p},t=0,\ldots,N}$ sekwencji $y$ i . Wektor ${\ displaystyle t}$ systemu w czasie ${\ Displaystyle x (t) \ in \ mathbb {R} ^ {n}}$ i ${\ displaystyle n}$ to kolejność modelu systemu. Z pary wejście / $}$ chciałoby się odzyskać macierze stan początkowy $displaystyle A, B, C, D$ . Ten problem można również postrzegać jako problem uzupełniania macierzy niskiego rzędu.

Lokalizacja internetu rzeczy (IoT).

Problem lokalizacji (lub pozycjonowania globalnego) pojawia się naturalnie w sieciach czujników IoT. Problem polega na odzyskaniu mapy czujnika w przestrzeni euklidesowej z lokalnego lub częściowego zestawu odległości parami. Zatem jest to problem uzupełniania macierzy o randze drugiej, jeśli czujniki znajdują się w płaszczyźnie 2-D, i trzeciej, jeśli znajdują się w przestrzeni 3-D.

Odzyskiwanie sieci społecznościowych

Większość rzeczywistych sieci społecznościowych ma macierze odległości niskiego rzędu. Kiedy nie jesteśmy w stanie zmierzyć całej sieci, co może wynikać z takich przyczyn, jak prywatne węzły, ograniczona pamięć lub zasoby obliczeniowe, znamy tylko ułamek wpisów dotyczących odległości. Sieci przestępcze są dobrym przykładem takich sieci. Do odzyskania tych nieobserwowanych odległości można użyć Matrix Completion niskiego poziomu.

Zobacz też

• Regularyzacja macierzy
• Nagroda Netflixa
• Filtrowanie zespołowe
• Identyfikacja systemu
• Optymalizacja wypukła
• Przypisanie