Detta dokument handlar om problemet med att återställa en okänd matris från en liten del av dess poster. Detta är känt som matrisen slutföra problem, och kommer upp i ett stort antal program, inklusive den berömda Netflix Prize och andra liknande frågor i samarbete filtrering. I allmänhet, exakt återhämtning av en matris från ett litet antal poster är omöjligt, men vetskapen om att den okända matrisen har låg rang radikalt ändrar denna premiss, vilket gör sökandet efter lösningar meningsfullt. I detta dokument presenteras optimala resultat som kvantifierar det minsta antal poster som krävs för att återställa en matris av rank r exakt med någon metod som helst (informationsteoretisk gräns). Ännu viktigare, tidningen visar att, under vissa osammanhängande antaganden om de singular vektorer av matrisen, återhämtning är möjligt genom att lösa en bekväm konvex program så snart antalet poster är på ordningen av informationen teoretiska gränsen (upp till logaritmiska faktorer). Detta konvexa program finner helt enkelt, bland alla matriser som överensstämmer med de observerade posterna, att med minsta nukleär norm. Som ett exempel, Vi visar att på ordningen för nr log(n) prover behövs för att återställa en slumpmässig n 2 n matris av rank r med någon metod, och för att vara säker, nukleär norm minimering lyckas så snart antalet poster är av formen nrpolylog(n). Index Terms-Duality i optimering, fri sannolikhet, lågrankade matriser, matriskomplettering, nukleär normminimering, slumpmässiga matriser och tekniker från slumpmässig matristeori, semidefinit programmering.
Candes och Tao REF härleder gränser för det minsta antal poster som behövs för slutförande av en matris med fasta rank; de introducerar också ett konvext program för matriskomplettering som fungerar nära den optimala hastigheten.
The Power of Convex Relaxation: Near-Optimal Matrix Completion
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}