Detta dokument introducerar en ny algoritm för att approximera matrisen med minimal kärnnorm bland alla matriser som följer en uppsättning konvexa begränsningar. Detta problem kan förstås som konvex avslappning av en rangminimering problem, och uppstår i många viktiga applikationer som i uppgiften att återställa en stor matris från en liten delmängd av sina poster (det berömda Netflix problemet). Off-the-shälf algoritmer såsom inre punkt metoder är inte direkt tillgängliga för stora problem av detta slag med över en miljon okända poster. Detta dokument utvecklar en enkel första-order och lätt att implementera algoritm som är extremt effektiv när det gäller att ta itu med problem där den optimala lösningen har låg rang. Algoritmen är iterativ och producerar en sekvens av matriser {X k, Y k } och vid varje steg, framför allt utför en mjuk-thresholding operation på singular värden av matrisen Y k. Det finns två anmärkningsvärda funktioner som gör detta attraktivt för låg-rank matris slutföra problem. Den första är att soft-thresholding operation tillämpas på en gles matris; den andra är att rangen av iteraterna {X k } är empiriskt nondecreasing. Båda dessa fakta gör det möjligt för algoritmen att utnyttja mycket minimalt lagringsutrymme och hålla beräkningskostnaden för varje iteration låg. På den teoretiska sidan tillhandahåller vi en konvergensanalys som visar att sekvensen av iterater konvergerar. På den praktiska sidan ger vi numeriska exempel där 1, 000×1, 000 matriser återvinns på mindre än en minut på en blygsam stationär dator. Vi visar också att vår strategi är mottaglig för mycket storskaliga problem genom att återhämta matriser av rang ca 10 med nästan en miljard okända från bara cirka 0,4% av deras provposter. Våra metoder är kopplade till den senaste litteraturen om lineariserade Bregman iterationer för l 1 minimering, och vi utvecklar ett ramverk där man kan förstå dessa algoritmer i termer av välkända Lagrange multiplikatoralgoritmer.
I vårt arbete tillämpar vi nuclear normen av matriser, och vi använder singular value threeling (SVT) metod REF för att lösa den låga rank minimization problem.
A Singular Value Thresholding Algorithm for Matrix Completion
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Computer Science', 'Mathematics']}