Matriskomplettering

Matrisfullbordande av en delvis avslöjad 5 x 5-matris med rank-1. Vänster: observerad ofullständig matris; Höger: resultat för matriskomplettering.

Matriskomplettering är uppgiften att fylla i de saknade posterna i en delvis observerad matris, vilket motsvarar att utföra dataimputation i statistik. Ett brett utbud av datauppsättningar är naturligt organiserade i matrisform. Ett exempel är filmvärderingsmatrisen, som visas i Netflix-problemet : Givet en betygsmatris där varje post $(i,j)$ representerar betyget för filmen $j$ av kund $i$ , om kund $i$ har sett film $j$ och annars saknas, vill vi förutsäga återstående poster för att ge bra rekommendationer till kunder om vad de ska se Nästa. Ett annat exempel är dokumenttermmatrisen : Frekvenserna av ord som används i en samling dokument kan representeras som en matris, där varje post motsvarar antalet gånger den associerade termen förekommer i det angivna dokumentet.

Utan några restriktioner på antalet frihetsgrader i den färdiga matrisen är detta problem underbestämt eftersom de dolda posterna kan tilldelas godtyckliga värden. Därför kräver vi några antaganden om matrisen för att skapa ett väl ställt problem , som att anta att det har maximal determinant, är positivt definitivt eller är lågt rangordnat.

Till exempel kan man anta att matrisen har en struktur med låg rangordning, och sedan försöka hitta den lägsta rangmatrisen eller, om rangordningen för den färdiga matrisen är känd, en matris med rang $r$ som matchar de kända posterna . Illustrationen visar att en delvis avslöjad rank-1-matris (till vänster) kan kompletteras med nollfel (till höger) eftersom alla rader med saknade poster bör vara samma som den tredje raden. När det gäller Netflix-problemet förväntas betygsmatrisen vara låg, eftersom användarpreferenser ofta kan beskrivas av ett par faktorer, såsom filmgenre och tidpunkt för släpp. Andra applikationer inkluderar datorseende, där saknade pixlar i bilder måste rekonstrueras, detektering av den globala positioneringen av sensorer i ett nätverk från partiell distansinformation och lärande i flera klasser . Matriskompletteringsproblemet är i allmänhet NP-hårt , men under ytterligare antaganden finns det effektiva algoritmer som uppnår exakt rekonstruktion med hög sannolikhet.

I statistisk inlärningssynpunkt är matriskompletteringsproblemet en tillämpning av matrisregularisering som är en generalisering av vektorregularisering . Till exempel, i problemet med att slutföra matrisen med låg rang kan man tillämpa regulariseringsstraffet i form av en kärnkraftsnorm $R(X)=\lambda \|X\|_ {*}$

Färdigställande av matris med låg rangordning

En av varianterna av matriskompletteringsproblemet är att hitta den lägsta rankningsmatrisen $X$ som matchar matrisen ${\displaystyle M} , som vi vill återställa, för alla poster$ i uppsättningen $E$ av observerade poster. Den matematiska formuleringen av detta problem är följande:

${\begin{aligned}&{\underset {X}{\text{min}}}&{\text{ rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}$

Candès och Recht bevisade att med antaganden om urvalet av de observerade posterna och tillräckligt många urvalsposter har detta problem en unik lösning med hög sannolikhet.

En ekvivalent formulering, givet att matrisen $M$ som ska återställas är känd för att ha rang $r$ , är att lösa för $X$ där $X_{ij}=M_{ij}\;\;\forall i,j\in E$

Antaganden

Ett antal antaganden om urvalet av de observerade posterna och antalet provtagna poster görs ofta för att förenkla analysen och för att säkerställa att problemet inte är underbestämt .

Enhetligt urval av observerade poster

För att göra analysen genomförbar antas det ofta att uppsättningen $E$ av observerade poster och fast kardinalitet samplas likformigt slumpmässigt från samlingen av alla delmängder av poster av kardinalitet $|E|$ . För att ytterligare förenkla analysen antas istället att $E$ är konstruerad av Bernoulli sampling , dvs att varje post observeras med sannolikhet $p$ . Om $p$ är satt till ${\frac {N}{mn}}$ där $N$ är den önskade förväntade kardinaliteten av ${\displaystyle E} ,$ och $m,\;n$ är matrisens dimensioner (låt $m<n$ utan förlust av generalitet), $|E|$ ligger inom $O(n\log n)$ av $N$ med hög sannolikhet, så Bernoulli-sampling är en bra approximation för enhetlig sampling. En annan förenkling är att anta att ingångarna provas oberoende och med ersättning.

Nedre gräns för antal observerade poster

Antag att $m$ av $n$ -matrisen $M$ (med $m<n$ ) vi försöker återställa har rang $r$ . Det finns en informationsteoretisk nedre gräns för hur många poster som måste observeras innan $M$ kan rekonstrueras unikt. Mängden $m$ med $n$ matriser med rangordning mindre än eller lika med $r$ är en algebraisk variant i ${\mathbb {C} }^ {m\times n}$ med dimension $(n+m)rr^{2}$ . Med detta resultat kan man visa att minst $4nr-4r^{2}$ -poster måste observeras för matriskomplettering i ${\mathbb {C} } ^{n\times n}$ för att få en unik lösning när $r\leq n/2$ .

För det andra måste det finnas minst en observerad post per rad och kolumn i $M$ . Singularvärdesuppdelningen av $M$ ges av $U\Sigma V^{\dolk$ } . Om rad $i$ inte observeras är det lätt att se den $i^{\text{th}}$ höger singularvektorn för ${\displaystyle M} ,$ v $\displaystyle v_{ i}}$ , kan ändras till något godtyckligt värde och fortfarande ge en matris som matchar $M$ över uppsättningen av observerade poster. På liknande sätt, om kolumn $j$ inte observeras, den $j^{\text{th}}$ vänstersingularvektorn för $M$ , $u_{i}$ kan vara godtycklig. Om vi ​​antar Bernoulli-sampling av uppsättningen observerade poster, kupongsamlareffekten att poster i storleksordningen $O(n\log n)$ måste observeras för att säkerställa att det finns en observation från varje rad och kolumn med hög sannolikhet.

Genom att kombinera de nödvändiga villkoren och anta att $r\ll m,n$ (ett giltigt antagande för många praktiska tillämpningar), den nedre gränsen för antalet observerade poster som krävs för att förhindra problemet med matriskomplettering från att vara underbestämd är i storleksordningen $nr\log n$ .

Brist på sammanhang

Begreppet inkoherens uppstod i komprimerad avkänning . Det introduceras i samband med matriskomplettering för att säkerställa att singularvektorerna för $M$ inte är för "glesa" i den meningen att alla koordinater för varje singularvektor är av jämförbar storlek istället för att bara några få koordinater har betydligt större magnituder. Standardbasvektorerna är då oönskade som singulära vektorer, och vektorn ${\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\ \\vdots \\1\end{bmatrix}}$ i $\mathbb {R} ^{n}$ är önskvärt. Som ett exempel på vad som kan gå fel om singularvektorerna är tillräckligt "glesa", betrakta $m$ med $n$ -matrisen ${\begin{bmatrix}1&0& \cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}$ med singularisvärdesuppdelning $I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}$ . Nästan alla poster i $M$ måste samplas innan den kan rekonstrueras.

Candès och Recht definierar koherensen av en matris $U$ med kolumnutrymme och $r-$ dimensionellt delrum av $\mathbb {R} ^{n}$ som $\mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i }\|^{2}$ , där $P_{U}$ är den ortogonala projektionen på $U$ . Inkoherens hävdar sedan att givet singularvärdesuppdelningen $U\Sigma V^{\dagger }$ av $m$ med $n$ -matrisen $M$ ,

1. $\mu (U),\;\mu (V)\leq \mu _{0}$
2. Inmatningarna för ${\displaystyle \sum _{k}u_{k}v_{k}^{\dolk }} har$ magnituder övre gränsad av $\mu _{ 1}{\sqrt {\frac {r}{mn}}}$

för några $\mu _{0},\;\mu _{1}$ .

Matriskomplettering med låg rankning med brus

I verkliga tillämpningar observerar man ofta bara ett fåtal poster skadade åtminstone av en liten mängd brus. Till exempel i Netflix-problemet är betygen osäkra. Candès och Plan visade att det är möjligt att fylla i de många saknade posterna i stora lågrankade matriser från bara några bullriga prover genom att minimera kärnnormerna. Den bullriga modellen förutsätter att vi observerar

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

där ${Z_{ij}:(i,j)\in \Omega }$ är en brusterm. Observera att bruset kan vara antingen stokastiskt eller deterministiskt. Alternativt kan modellen uttryckas som

$P_{\Omega }(Y)=P_{\Omega }(M)+P_{\Omega }(Z),$

där $Z$ är en $n\times n$ matris med poster $Z_{ij}$ för $(i,j) \in \Omega$ om man antar att $\|P_{\Omega }(Z)\|_{F}\leq \delta$ för vissa $\delta >0$ .För att återställa den ofullständiga matrisen försöker vi lösa följande optimeringsproblem:

${\begin{aligned}&{\underset {X}{\text{min}}}&\|X\| _{*}\\&{\text{med förbehåll för}}&\|P_{\Omega }(XY)\|_{F}\leq \delta \\\end{aligned}}$

Bland alla matriser som överensstämmer med data, hitta den med lägsta kärnkraftsnorm. Candès och Plan har visat att denna rekonstruktion är korrekt. De har bevisat att när perfekt ljudlös återhämtning inträffar, då är matriskomplettering stabil gentemot störningar. Felet är proportionellt mot brusnivån $\delta$ . Därför, när brusnivån är liten, är felet litet. Här följer inte matriskompletteringsproblemet den begränsade isometriska egenskapen (RIP). För matriser skulle RIP anta att provtagningsoperatören lyder

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

för alla matriser $X$ med tillräckligt liten rang och $\delta <1$ tillräckligt liten. Metoderna är också tillämpliga på glesa signalåterställningsproblem där RIP inte håller.

Fullbordat matris med hög rang

Den höga matriskompletteringen i allmänhet är NP-Hard . Med vissa antaganden kan dock en ofullständig matris med hög rang eller till och med full rangmatris slutföras.

Eriksson, Balzano och Nowak har övervägt problemet med att komplettera en matris med antagandet att matrisens kolumner tillhör en förening av flera lågrankade delrum. Eftersom kolumnerna tillhör en förening av delutrymmen, kan problemet ses som en version med saknade data av klustringsproblemet för underutrymmet . Låt $X$ vara en $n\ gånger N$ matris vars (fullständiga) kolumner ligger i en union av högst $k$ underrymden, var och en av $rank\leq r<n$ , och antag $N\gg kn$ . Eriksson, Balzano och Nowak visade att under milda antaganden kan varje kolumn i $X$ perfekt återställas med hög sannolikhet från en ofullständig version så länge som minst $CrN\log ^{2}(n)$ inmatningar av $X$ observeras slumpmässigt enhetligt, med $C>1$ en konstant beroende på de vanliga inkoherensförhållandena, det geometriska arrangemanget av delrum och fördelning av kolumner över delutrymmena.

Algoritmen innefattar flera steg: (1) lokala stadsdelar; (2) lokala delrum; (3) förfining av delrum; (4) komplett matris. Denna metod kan appliceras på internetdistansmatriskomplettering och topologiidentifiering.

Algoritmer för komplettering av matris med låg rang

Olika matriskompletterande algoritmer har föreslagits. Dessa inkluderar konvex avslappningsbaserad algoritm, gradientbaserad algoritm och alternerande minimeringsbaserad algoritm.

Konvex avslappning

Rangminimeringsproblemet är NP-hårt . Ett tillvägagångssätt, som föreslagits av Candès och Recht, är att skapa en konvex relaxation av problemet och minimera kärnnormen ‖ $\displaystyle \|M\|_{*}} ($ som ger summan av singularvärdena för $M$ ) istället för ${\text{rank}}(M)$ (som räknar antalet singularvärden som inte är noll för $M$ ). Detta är analogt med att minimera L1- normen snarare än L0- normen för vektorer. Den konvexa relaxationen kan lösas med semidefinite programmering (SDP) genom att notera att optimeringsproblemet är likvärdigt med

${\begin{aligned }&{\underset {W_{1},W_{2}}{\text{min}}}&&{\text{trace}}(W_{1})+{\text{trace}}(W_{2 })\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix}W_{1}&X\\ X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{aligned}}$

Komplexiteten i att använda SDP för att lösa den konvexa relaxationen är $O({\text{max}}(m,n)^{4})$ . Toppmoderna lösare som SDPT3 kan bara hantera matriser med storlek upp till 100 gånger 100. En alternativ första ordningens metod som ungefär löser den konvexa avslappningen är Singular Value Thresholding Algorithm introducerad av Cai, Candès och Shen.

Candès och Recht visar, med hjälp av studien av slumpvariabler på Banach-utrymmen , att om antalet observerade poster är i storleksordningen $\ max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\ log n$ (antag utan förlust av generalitet $m<n$ ), rangminimeringsproblemet har en unik lösning som också råkar vara lösningen på dess konvexa relaxation med sannolikhet $1-{\frac {c}{n^{3}}}$ för någon konstant $c$ . Om rangordningen för $M$ är liten ( ${\displaystyle r\leq {\frac {n^{0.2}}{\mu _{0}}}} ), är$ storleken på uppsättning observationer reduceras till storleksordningen $\mu _{0}n^{1.2}r\log n$ . Dessa resultat är nära optimala, eftersom det minsta antalet poster som måste observeras för att matriskompletteringsproblemet inte ska vara underbestämt är i storleksordningen $nr\log n$ .

Detta resultat har förbättrats av Candès och Tao. De uppnår gränser som skiljer sig från de optimala gränserna endast genom polylogaritmiska faktorer genom att stärka antagandena. Istället för inkoherensegenskapen antar de den starka inkoherensegenskapen med parametern $\mu _{3}$ . Denna egenskap säger att:

1. $|\langle e_{a},P_{U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'}|\leq \mu _{3}{\frac {\sqrt {r}}{m}}$ för $a,a'\leq m$ och $|\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}$ för $b,b'\leq n$
2. Posterna för $\sum _{i}u_{i}v_{i}^{\dolk }$ begränsas i storlek av $\mu _{ 3}{\sqrt {\frac {r}{mn}}}$

Intuitivt hävdar stark inkoherens av en matris $U$ att de ortogonala projektionerna av standardbasvektorer till $U$ har magnituder som har hög sannolikhet om de singulära vektorerna fördelades slumpmässigt.

Candès och Tao finner att när $r$ är $O(1)$ och antalet observerade poster är i storleksordningen $\ mu _{3}^{4}n(\log n)^{2}$ , rangminimeringsproblemet har en unik lösning som också råkar vara lösningen på dess konvexa relaxation med sannolikhet $1-{\frac {c}{n^{3}}}$ för någon konstant $c$ . För godtycklig ${\displaystyle r} är$ antalet observerade poster som är tillräckligt för att detta påstående är sant i storleksordningen $\mu _{3}^{2}nr (\log n)^{6}$

En annan konvex avslappningsmetod är att minimera Frobenius-kvadratnormen under en rangbegränsning. Detta motsvarar att lösa

${\begin{aligned}&{\underset {X}{\text{min}}}&&\Vert X\Vert _{F}^{2}\\&{\text{med förbehåll för}}&&X_ {ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{Rank}}(X)\leq k.\end{aligned}}$

Genom att introducera en ortogonal projektionsmatris $Y$ (vilket betyder $Y^{2}=Y,Y=Y'$ ) för att modellera rangordningen för $X$ via $X=YX,{\text{trace}}(Y)\leq k$ och med detta problems konvexa relaxation får vi följande semidefinita program

${ \begin{aligned}&{\underset {X,Y,\theta }{\text{min}}}&&{\text{trace}}(\theta )\\&{\text{med förbehåll för}}&&X_{ ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{trace}}(Y)\leq k,0\preceq Y\preceq I\\&&&{\begin{ pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}$

Om Y är en projektionsmatris (dvs. har binära egenvärden) i denna relaxation, då är relaxationen tät. Annars ger det en giltig nedre gräns för det övergripande målet. Dessutom kan den omvandlas till en genomförbar lösning med ett (något) större mål genom att girigt avrunda egenvärdena för Y. Anmärkningsvärt nog kan denna konvexa avslappning lösas genom alternerande minimering på X och Y utan att lösa några SDP:er, och därmed skalar den bortom de typiska numeriska gränserna för toppmoderna SDP-lösare som SDPT3 eller Mosek.

Detta tillvägagångssätt är ett specialfall av en mer allmän omformuleringsteknik, som kan tillämpas för att erhålla en giltig nedre gräns för alla lågrankade problem med ett spår-matris-konvext mål.

Gradient nedstigning

Keshavan, Montanari och Oh överväger en variant av matriskomplettering där rangordningen av m $\displaystyle m}$ med $n$ matris ${\displaystyle M} ,$ som ska återställas, är känd för att vara ${\ displaystyle r}$ . De antar Bernoulli-sampling av poster, konstant bildförhållande ${\displaystyle {\frac {m}{n}}} ,$ gränsad storlek på poster av $M$ (låt den övre gränsen vara $M_ {\text{max}}$ ), och konstant tillståndstal ${\frac {\sigma _{1}}{\sigma _{r}}}$ (där $\ sigma _{1}$ och $\sigma _{r}$ är de största och minsta singularvärdena för $M$ ). Vidare antar de att de två inkoherensvillkoren är uppfyllda med $\mu _{0}$ och $\mu _{1}{\frac {\sigma _{1}}{ \sigma _{r}}}$ där $\mu _{0}$ och $\mu _{1}$ är konstanter. Låt $M^{E}$ vara en matris som matchar $M$ på uppsättningen $E$ av observerade poster och är 0 någon annanstans. De föreslår sedan följande algoritm:

1. Trimma $M^{E}$ genom att ta bort alla observationer från kolumner med grad större än ${\frac {2|E|}{n}}$ genom att ställa in posterna i kolumnerna till 0. Ta på liknande sätt bort alla observationer från rader med grad större än ${\frac {2|E|}{n}}$ .
2. Projektera $M^{E}$ på dess första $r$ huvudkomponenter . Kalla den resulterande matrisen ${\text{Tr}}(M^{E})$ .
3. Lös $\min _{ X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\summa _{i,j\in E}(M_{ij} -(XSY^{\dolk })_{ij})^{2}+\rho G(X,Y)$ där $G(X,Y)$ är någon regulariseringsfunktion av gradient nedstigning med linjesökning . Initiera $X,\;Y$ vid $X_{0},\;Y_{0}$ där ${\text{ Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dolk }$ . Ställ in $G(X,Y)$ som en funktion som tvingar $X,\;Y$ att förbli osammanhängande under hela gradientnedgången om $X_{0}$ och $Y_{0}$ är osammanhängande.
4. Returnera matrisen $XSY^{\dolk }$ .

Steg 1 och 2 i algoritmen ger en matris ${\text{Tr}}(M^{E})$ mycket nära den sanna matrisen $M$ (uppmätt med root mean square error (RMSE) ) med hög sannolikhet. I synnerhet med sannolikhet $1-{\frac {1}{n^{3}}}$ , ${\displaystyle {\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F} ^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}} för någon konstant C {\$ displaystyle $}$ . $\|\cdot \|_{F}$ betecknar Frobenius- normen . Observera att alla antaganden inte behövs för att detta resultat ska hålla. Inkoherensvillkoret spelar till exempel bara in i exakt rekonstruktion. Slutligen, även om trimning kan verka kontraintuitivt eftersom det involverar att kasta ut information, säkerställer det att projicering av $M^{E}$ på dess första $r$ huvudkomponenter ger mer information om den underliggande matrisen ${\ displaystyle M}$ än om de observerade posterna.

I steg 3 kan utrymmet för kandidatmatriserna $X,\;Y$ reduceras genom att notera att det inre minimeringsproblemet har samma lösning för ( $\displaystyle (X,Y)}$ som för $(XQ,YR)$ där $Q$ och $R$ är ortonormala $r$ av $r$ -matriser. Sedan gradientnedstigning utföras över korsprodukten av två Grassman-grenrör . Om $r\ll m,\;n$ och den observerade inmatningsmängden är i ordningen $nr\log n$ , är matrisen som returneras av steg 3 exakt $M$ . Då är algoritmen ordningsoptimal, eftersom vi vet att för att matriskompletteringsproblemet inte ska vara underbestämt måste antalet poster vara i storleksordningen $nr\log n$ .

Alternerande minsta kvadraters minimering

Alternerande minimering representerar ett allmänt tillämpbart och empiriskt framgångsrikt tillvägagångssätt för att hitta lågrankade matriser som bäst passar de givna uppgifterna. Till exempel, för problemet med att färdigställa matrisen med låg rang, tros denna metod vara en av de mest exakta och effektiva och utgjorde en viktig del av det vinnande bidraget i Netflix-problemet. I den alternerande minimeringsmetoden skrivs den låga målmatrisen i en bilinjär form :

$X=UV^{T}$ ;

Algoritmen växlar sedan mellan att hitta den bästa $U$ och den bästa $V$ . Medan det övergripande problemet är icke-konvext, är varje delproblem typiskt konvext och kan lösas effektivt. Jain, Netrapalli och Sanghavi har gett en av de första garantierna för prestanda av alternerande minimering för både matriskomplettering och matrisavkänning.

Den alternerande minimeringsalgoritmen kan ses som ett ungefärligt sätt att lösa följande icke-konvexa problem:

${\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2} \\\end{aligned}}$

AltMinComplete Algorithm som föreslagits av Jain, Netrapalli och Sanghavi listas här:

1. Ingång : observerad uppsättning $\Omega$ , värden $P_{\Omega }(M)$
2. Partitionera $\Omega$ i $2T+1$ delmängder $\Omega _{0},\cdots ,\Omega _{2T}$ med varje element av $\Omega$ som tillhör en av $\Omega _{t}$ med lika sannolikhet (sampling med ersättning)
3. ${\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{ 0}}(M),k)$ dvs topp- $k$ vänster singular vektorer av ${\frac {1}{p}}P_{\Omega _{ 0}}(M)$
4. Clipping : Ställ in alla element i ${\hat {U}}^{0}$ som har en magnitud större än ${\frac {2\mu {\sqrt {k}}} {\sqrt {n}}}$ för att nollställa och ortonormalisera kolumnerna i ${\hat {U}}^{0}$
5. för $t=0,\cdots ,T-1$ gör
6. $\quad {\hat {V}}^{t+1}\leftarrow {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T }-M)\|_{F}^{2}$
7. $\quad {\hat {U}}^ {t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\times k}}\|P_{\Omega _{T+t+1}}(U( {\hat {V}}^{t+1})^{T}-M)\|_{F}^{2}$
8. slut för
9. Returnera $X={\hat {U}}^{T}({\hat {V}}^{T})^{T}$

De visade att genom att observera $|\Omega |=O(({\frac {\sigma _{1} ^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))$ slumpmässiga inmatningar av en inkoherent matris $M$ , AltMinComplete-algoritmen kan återställa $M$ i $O(\log(1/\epsilon ))$ steg . När det gäller provkomplexitet ( $|\Omega |$ ), teoretiskt sett, kan alternerande minimering kräva en större $\Omega$ än konvex avslappning. Emellertid tycks det inte vara fallet, vilket innebär att urvalets komplexitetsgränser kan skärpas ytterligare. När det gäller tidskomplexitet visade de att AltMinComplete behöver tid

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

Det är värt att notera att även om konvexa avslappningsbaserade metoder har rigorös analys, är alternerande minimeringsbaserade algoritmer mer framgångsrika i praktiken.

Ansökningar

Flera tillämpningar av matriskomplettering sammanfattas av Candès och Plan enligt följande:

Kollaborativ filtrering

Kollaborativ filtrering är uppgiften att göra automatiska förutsägelser om en användares intressen genom att samla in smakinformation från många användare. Företag som Apple, Amazon, Barnes och Noble och Netflix försöker förutsäga sina användarpreferenser utifrån delvis kunskap. I dessa typer av matriskompletterande problem anses den okända fullständiga matrisen ofta vara låg rang, eftersom endast ett fåtal faktorer vanligtvis bidrar till en individs smak eller preferens.

Systemidentifiering

I kontroll skulle man vilja passa in en diskret-tid linjär tid-invariant tillstånd-rum modell

${\begin{aligned}x(t+1)& =Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aligned}}$

till en sekvens av ingångar $u(t)\in \mathbb {R} ^{m}$ och utgångar $y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N$ . Vektorn $x(t)\in \mathbb {R} ^{n}$ är systemets tillstånd vid tidpunkten $t$ och $n$ är ordningen på systemmodellen. Från input/output-paret skulle man vilja återställa matriserna $A,B,C,D$ och initialtillståndet $x(0)$ . Detta problem kan också ses som ett problem med att färdigställa matrisen med låg rangordning.

Internet of things (IoT) lokalisering

Lokaliseringsproblemet (eller global positionering) dyker upp naturligt i IoT-sensornätverk. Problemet är att återställa sensorkartan i det euklidiska rymden från en lokal eller partiell uppsättning parvisa avstånd. Det är alltså ett problem med matriskomplettering med rang två om sensorerna är placerade i ett 2-D-plan och tre om de är i ett 3-D-utrymme.

Återställning av sociala nätverk

De flesta av de verkliga sociala nätverken har låga distansmatriser. När vi inte kan mäta hela nätverket, vilket kan bero på till exempel privata noder, begränsad lagring eller beräkningsresurser, har vi bara en bråkdel av distansposterna kända. Kriminella nätverk är ett bra exempel på sådana nätverk. Low-rank Matrix Completion kan användas för att återställa dessa oobserverade avstånd.

Se även

• Matrisregularisering
• Netflix-priset
• Kollaborativ filtrering
• Systemidentifiering
• Konvex optimering
• Tillskrivning