Detta papper handlar om en grundläggande klass av konvex matris optimering problem. Den presenterar den första algoritmen som använder optimal lagring och sannolikt beräknar en lågrankad approximation av en lösning. Särskilt när alla lösningar har låg rang konvergerar algoritmen till en lösning. Denna algoritm, SketchyCGM, ändrar en standard konvex optimeringsschema, den villkorliga lutningsmetoden, för att lagra endast en liten randomiserad skiss av matrisvariabeln. Efter optimeringen avslutas extraherar algoritmen en låggradig approximation av lösningen från skissen. I motsats till icke konvexa heuristiker är garantierna för Sketchy-CGM inte beroende av statistiska modeller för problemdata. Numeriskt arbete visar fördelarna med SketchyCGM över heuristik. Denna uppsats diskuterar en grundläggande klass av konvex matrisoptimering problem med lågrankade lösningar. Vi hävdar att det största hindret som hindrar oss från att lösa dessa problem i stor skala inte är aritmetisk, utan lagring. Vi uppvisar den första bevisligen korrekta algoritmen för dessa problem med optimal lagring. För att förklara utmaningen, anser vi problemet med low-rank matris avslutning. Låt X  till R m×n vara en okänd matris, men anta att en gräns r på rank av X är tillgänglig, där r min {m, n}. Antag att vi registrerar bullriga observationer av en delmängd E av poster från matrisen: Variablerna ij  på R-modellen (okänd) buller. Målet är att approximera den fullständiga matrisen X. Matrix slutförande uppstår i maskininlärning applikationer, såsom rekommendationssystem [34]. Vi kan rama in matrisen slutföra problemet som en rank-konstruerad optimering: I allmänhet, formuleringen (1) är intractable. Istället går vi tillbaka till ett dragbart konvext problem [7, 34] : Schatten 1-norm · S1 returnerar summan av de enskilda värdena i sitt argument; det är en effektiv proxy för rangen [13]. Justering av värdet på parametern α modulerar rangen för en lösning X av (2). Om vi har tillräckligt med data och väljer α väl, förväntar vi oss att varje lösning X approximerar målet matris X. Konvexa problem (2) är ofta en bra modell för matriskomplettering när antalet observationer är lika många (r(m + n)), där Õ undertrycker log-liknande faktorer; se [7, 34]. Vi kan skriva en rank-r approximation till en lösning X med hjälp av r(m + n) parametrar. Således kan vi uttrycka problemet och en ungefärlig lösning med Õ (r(m + n) lagring. Ändå behöver vi helt mn siffror för att uttrycka beslut variabel X för optimeringsproblem (2). Kostnaden för lagring av beslutsvariabeln hindrar oss från att lösa storskaliga fall av (2), även utan att oroa oss för aritmetik. Denna diskrepans väcker en fråga: Finns det en algoritm som beräknar en ungefärlig lösning till (2) med den optimala lagringen Õ (r(m + n))?  Här är ett annat exempel på samma situation. Fixa en vektor x  på C n. Antag att vi förvärvar d bullriga kvadratiska mätningar av x med formen A i  på C n är kända mätvektorer, och i R modellen mätning buller. Med tanke på data b och vektorerna a i, fas hämtning problem ber oss att rekonstruera x upp till en global fas skifte. Fas hämtning problem är vanligt i avbildning vetenskap eftersom det är lättare att mäta intensiteten av ljus än dess fas. I praktiken, vektorerna a i är strukturerade eftersom de återspeglar fysiken i bildsystemet. För mer information, se bilaga B.3 och exemplen i [3, 8, 10, 22]. Låt oss skissera ett konvext tillvägagångssätt [3, 8, 10, 22] för fashämtningsproblemet. Data (3) uppfyller Således kan vi formulera fas hämtning som Nu, passera till konvex problem Vi kan uppskatta parametern α  på R + från a i och b; se [39, Sec. II) och förordning (EEG) nr 4064/89, i dess lydelse enligt rådets förordning (EEG) nr 4064/89 av den 21 december 1989 om tillämpningsföreskrifter för rådets förordning (EEG) nr 4064/89 om tillämpningsföreskrifter för rådets förordning (EEG) nr 4064/89 om tillämpningsföreskrifter för rådets förordning (EEG) nr 4064/89 om harmonisering av medlemsstaternas lagstiftning rörande omsättningsskatter, rådets förordning (EEG) nr 4064/89 om harmonisering av medlemsstaternas lagstiftning rörande omsättningsskatter, rådets förordning (EEG) nr 4064/89 om harmonisering av medlemsstaternas lagstiftning rörande omsättningsskatter och rådets förordning (EEG) nr 4064/89 om tillämpningsföreskrifter för rådets förordning (EEG) nr 4064/89 om harmonisering av medlemsstaternas lagstiftning rörande omsättningsskatter. För att uppskatta den sanna vektorn x, Vi beräknar en topp eigenvector x av en lösning till (5). Detta förfarande är ofta ett effektivt tillvägagångssätt för fashämtning när antalet mätningar d =  på (n); se [36, Sec. Detta är en av de viktigaste orsakerna till att det inte längre är möjligt att uppnå detta mål. Än en gång känner vi igen en diskrepans. Problemdata b  på R d och den ungefärliga lösningen x  på C n använda lagring  på (n), men matrisvariabeln i (5) kräver  på (n 2 ) lagring. Vi kan fråga: Finns det en algoritm som beräknar en ungefärlig lösning till (5) genom att använda den optimala lagringen (n)? Matrix komplettering och fas hämtning är exempel på konvex low-rank matrisoptimering (CLRO) problem. Informellt, denna klass innehåller konvex optimering problem vars beslut variabel är en matris och vars lösningar är (nära) låg rang. Dessa problem uppstår ofta som konvexa avslappningar av rankkonstriktade problem; men konvexa formuleringar är viktiga i sin egen rätt. Det har förekommit omfattande empiriskt och teoretiskt arbete för att validera användningen av CLRO i ett spektrum av tillämpningar. Se till exempel [7, 8, 13, 16, 22]. Under de senaste 20 åren har optimeringsforskare utvecklat en mängd olika algoritmer för CLRO-problem. Förvånansvärt nog saknar varje extern metod garantier för lagring eller konvergens (eller båda). Convex optimeringsalgoritmer dominerade den tidiga litteraturen om algoritmer för CLRO. De inledande ansträngningarna, såsom [21], inriktades på inre punktmetoder, vars lagring och aritmetiska kostnader förbjuds. För att lösa detta problem vände sig forskarna till första ordningens konvexa algoritmer, inklusive buntmetoder [20], (accelererade) proximal gradientmetoder [2, 32, 35] och den villkorliga gradientmetoden (CGM) [11, 15, 19, 23, 25]. Konvexa algoritmer är garanterade att lösa en CLRO. De kommer med en fullständig teori, inklusive rigorösa stoppkriterier och gränser för konvergensnivåer. De njuter av robusta prestanda i praktiken. Å andra sidan, konvexa algoritmer från litteraturen inte skala tillräckligt bra för att lösa stora CLRO-problem eftersom de fungerar på och lagra full storlek matriser. CGM iteration tippas ibland som en låglagringsmetod för CLRO [23]. CGM är garanterad att öka rangen av en iterat med högst en per iteration. Men algoritmen konvergerar långsamt, så mellanliggande iterater kan ha mycket hög rang. CGM varianter, såsom [31, 39], som kontrollerar rangen av iterater saknar lagringsgarantier eller kanske inte konvergera till en global optimal. På senare tid har många utredare sökt hjälp i icke konvexa heuristiker för att lösa CLROs. Denna arbetslinje beror på faktoriseringsidén hos Burer & Monteiro [6], som skriver om matrisvariabeln som en produkt av två lågrankade faktorer. Det finns många heuristiska procedurer, t.ex. [4] [5] [6] 24], som använder smart initiering och icke-linjära programmeringsprogram i ett försök att optimera faktorerna direkt. De resulterande algoritmerna kan ha optimala lagringskostnader, och de kan uppnå en snabb takt av lokal konvergens. Det har gjorts en intensiv ansträngning för att motivera tillämpningen av icke konvexa heuristiker för CLRO. För att göra det skapar forskarna ofta okontrollerbara statistiska antaganden om problemdata. Till exempel i matrisen slutföra problem (2) är det vanligt att anta att posterna i matrisen avslöjas enligt några idealisk sannolikhetsfördelning [7, 24]. När dessa antaganden misslyckas, kan icke konvexa heuristiker konvergera till fel punkt, eller också kan de till och med avvika. Yurtsever, Udell, Tropp, Cevhers bidrag. Detta dokument förklarar hur man utökar den konvexa optimeringsalgoritmen CGM för att få en ungefärlig lösning till en klass av CLRO-problem med optimal lagring. Vår algoritm fungerar ungefär som CGM, men den bildar aldrig matrisvariabeln explicit. Istället behåller vi en liten randomiserad skiss av matrisvariabeln under iterationens gång med hjälp av en skräddarsydd skissmetod [37]. Efter optimeringsmetoden konvergerar extraherar vi en ungefärlig lösning från skissen. Denna teknik uppnår optimal lagring, men konvergerar under samma förhållanden och med samma garantier som CGM. Sammanfattningsvis presenterar detta dokument en lösning på de problem som ställs ovan: den första algoritmen för konvex lowrank matrisoptimering problem som bevisligen använder optimal lagring för att beräkna en ungefärlig lösning. Vi skriver · för den euklideiska normen, · F för Frobeniusnormen och · S1 för Schatten 1-normen (även kallad spårnormen eller atomnormen). Beroende på sammanhang, ·, · avser Euclidean eller Frobenius inre produkt. Symbolen * betecknar konjugatet införliva en vektor eller matris, liksom den angränsande av en linjär karta. Dolken † hänvisar till pseudoinversen. Symbolen [M ] r står för en bästa rank-r Frobenius-norm approximation av matrisen M. Funktionen dist F (M ; S) returnerar den minsta Frobeniusnorm avstånd från M till en uppsättning S. Symbolen betecknar semidefinit ordning. Vi använder data science tolkning av ordern notation O, Õ,  på. Låt oss börja med en generalisering av konvex matris avslutning formulering (2). I §5.5 återgår vi till psd-inställningen av fashämtningsproblemet (5). Vi anser att ett konvext program med en matrisvariabel: Den linjära operatören A : R m×n → R d och dess angränsande Varje koefficientmatris Vi tolkar A X som en uppsättning linjära mätningar av matrisen X. I matriskompletteringsproblemet (2) listar till exempel bilden A X de poster i X som indexerats av uppsättningen E. Funktionen f : R d → R är konvex och kontinuerligt differentierad. I många situationer är det naturligt att betrakta den objektiva funktionen som en förlust: f (A X) = förlust(A X; b) för en vektor b  på R d av uppmätta data. Genom att välja parametern α  på R + för att vara tillräckligt liten, kan vi ofta se till att varje minimator på (6) är låg-rank eller nära låg-rank. Vårt mål är att utveckla en praktisk algoritm som bevisligen beräknar en låggradig approximation av en lösning på problemet (6). För att kunna validera (6) som modell för en viss ansökan måste man genomföra en separat empirisk eller teoretisk studie. Vi tar inte upp denna fråga i vårt arbete. Anta att vi vill producera en låg nivå approximation till en lösning av en generisk instans av problemet (6). Vilken typ av förvaring kan vi hoppas uppnå? Det är tydligt att vi behöver  på (r(m + n)) siffror för att uttrycka en rank-r ungefärlig lösning till (6). Vi måste också förstå hur mycket extra lagring uppstår på grund av den specifika problematik (A, f ). Det är naturligt att instate en svart-box modell för den linjära kartan A, dess angränsande A *, och den objektiva funktionen f. För godtyckliga vektorer u A * z) och v A * z) v, antar att vi har rutiner som kan beräkna A (uv * ) och u * (A * z) och (A * z) v. Vi antar också rutiner för att utvärdera funktionen f och dess lutning f för alla argument z  till R d. Vi kan försumma lagring som används för att beräkna dessa primitiva. Varje algoritm som baseras på dessa primitiva måste använda lagrings- (m + n + d) bara för att representera sina utgångar. Under Black-box-modellen måste därför alla algoritmer som producerar en rank-r-lösning till en generisk instans av (6) använda lagringslösning (d + r(m + n)). Vi säger att en algoritm är lagring optimal om den uppnår denna gräns. Parametern d återspeglar ofta mängden data som vi har förvärvat, och den är vanligtvis mycket mindre än dimensionen mn av matrisvariabeln i (6). De problem som oroar oss är databegränsade, det vill säga d mn. Detta är den situation där en stark strukturell tidigare (t.ex. låg rang eller liten Schatten 1-norm) är avgörande för att anpassa data. Denna utmaning är vanlig i maskininlärningsproblem (t.ex. matriskomplettering för rekommendationssystem) samt i vetenskapliga tillämpningar (t.ex. fasinhämtning). Såvitt vi vet är ingen extant algoritm för (6) garanterad att producera en approximation av en optimal punkt och har också optimal lagringskostnad. Convex Low-Rank Matrix Optimering med Optimal Storage För att utveckla vår algoritm för modellproblemet (6) måste vi först beskriva en standardalgoritm som kallas den villkorliga gradientmetoden (CGM). Klassiska och samtida referenser inkluderar [11, 15, 19, 23, 25]. Här är CGM algoritmen för (6). Börja med en genomförbar punkt, såsom Vid varje iteration t = 0, 1, 2,...., beräkna en uppdatering riktning H t med hjälp av formlerna (u t, v t ) = MaxSingVec( A * ( till A X t )); MaxSingVec returnerar en vänster/höger par av maximal singular vektorer. Uppdatera beslutsvariabeln: där η t = 2/(t + 2). Konvexkombinationen (11) är fortfarande möjlig för (6) eftersom X t och H t är möjliga. CGM är en värdefull algoritm för (6) eftersom vi effektivt kan hitta rank-one uppdateringsriktningen H t med hjälp av den unika vektorberäkningen (10). Den svaga punkten av CGM är att rangen av X t normalt ökar med t, och topp rangen av en iterat X t är ofta mycket större än rangen av lösningen av (6). Se figurerna 6 och 7 för en illustration. CGM-algoritmen medger ett enkelt stoppkriterium. Med tanke på en suboptimal parameter ε > 0, stoppar vi CGM iterationen när dualitetsgapet δ t ≤ ε: Låt X vara en optimal punkt för (6). Det är inte svårt att visa [23, Sec. 2] att villkoret (12) säkerställer att det objektiva värdet f (A X t ) är ε-suboptimalt. Den CGM itererates sat- den CGM iteration (9)- (11) kräver  och (mn) lagring eftersom den upprätthåller m × n matris beslut variabel X t. Vi utvecklar en anmärkningsvärd förlängning av CGM som bevisligen beräknar en rank-r ungefärlig lösning till (6) med arbetslagring. (d + r(m + n)). Vårt tillvägagångssätt beror på två effektivitetsvinster: • Vi använder den lågdimensionella "dubbel" variabeln z t = A X t  på R d för att driva iterationen. • Istället för att lagra X t, underhåller vi en liten randomiserad skiss med storlek (r(m + n)). Det är lätt att uttrycka CGM iteration i termer av "dubbel" variabel z t = A X t. Vi kan naturligtvis skriva om formeln (10) för att beräkna rank-one uppdatering riktning H t i termer av z t. Vi får en uppdatering regel för z t genom att tillämpa den linjära kartan A till (11). På samma sätt kan stoppkriteriet (12) utvärderas med hjälp av z t och H t. Enligt modellen med black-box (8) har den dubbla formuleringen av CGM lagringskostnader (m + n + d). Ändå har den dubbla formuleringen en brist: den "löser" problemet (6), men vi vet inte lösningen! Vi måste också följa utvecklingen (11) av den primära beslutsvariabeln X t. I nästa underavsnitt summerar vi en randomiserad skissmetod [37] som gör det möjligt för oss att beräkna en exakt rank-r approximation av X t men fungerar med lagring (r(m + n)). Antag att X  till R m×n är en matris som presenteras för oss som en ström av linjära uppdateringar, som i (11). För en parameter r min {m, n}, vill vi behålla en liten skiss som gör det möjligt för oss att beräkna en rank-r approximation av den slutliga matrisen X. Låt oss sammanfatta en strategi som utvecklats i vårt dokument [37]. Rita och fixa två oberoende standardnormala matriser  på ett sätt som gör det möjligt för dig att få tag på två standardmatriser med k = 2r + 1;  ska R ×m med = 4r + 3. Skissen består av två matriser Y och W som fångar intervallet och sam-omfånget av X: Vi kan effektivt uppdatera skissen (Y, W ) för att återspegla en rank-en linjär uppdatering till X av formuläret Både lagringskostnaden för skissen och den aritmetiska kostnaden för en uppdatering är  till (r(m + n)). Följande förfarande ger en rang-r approximation X av den matris X som lagras i skissen (15). Yurtsever, Udell, Tropp, Cevher Matrisen Q har ortonormala kolumner som spänner över intervallet Y. De extra lagringskostnaderna för återuppbyggnaden är försumbara och den aritmetiska kostnaden för den är 2 (m + n). Se [37, §4.2] för intuitionen bakom denna metod. Det uppnår följande fel bundna. Teoret 1 (Återbyggnadsfel [37, Thm. (se avsnitt 5. 1 och 5. 1]). Fix en mål rank r. Låt X vara en matris, och låt (Y, W ) vara en skiss av X i formen (14-(15 ). Förfarandet (17) ger en rank-r matrisX med liknande gränser hålla med hög sannolikhet. Anmärkningar.................................................................................................. De skissstorleksparametrar (k, ) som visas i (14) rekommenderas för att balansera lagring mot återuppbyggnadskvalitet. Se [37] och vårt uppföljningsarbete för mer information och för andra skissmetoder. Vi är nu beredda att presentera SketchyCGM, en lagringsoptimal förlängning av CGM-algoritmen för konvexa problem (6). Denna metod ger en bevisligen korrekt lågvärdig approximation till en lösning på (6). Se Algoritm 1 för fullständig pseudokod. Rätta suboptimalitet ε och rank r. Rita och fixa standard normala matriser  och R n×k och  på R ×m som i (14). Initialisera iteratet och skisserna: Vid varje iteration t = 0, 1, 2,...., beräkna en uppdatering riktning via Lanczos eller via randomiserade SVD [17]: Ställ in inlärningshastigheten η t = 2/(t+2). Uppdatera iterat och de två skisserna: Iterationen fortsätter tills den utlöser stoppkriteriet: Vid varje iteration t kan vi bilda en rank-r ungefärlig lösningX t av modellproblemet (6) genom att åberopa förfarandet (17) med Y = Y t och W = W t. Antag att CGM iteration (9)- (11) genererar sekvensen (X t : t = 0, 1, 2,.. ) av beslutsvariabler och sekvensen (H t : t = 0, 1, 2,.. ) av uppdatering riktningar. Det är lätt att kontrollera att SketchyCGM iterationen (18- (20) upprätthåller loopinvarianterna z t = A X t och h t = A H t; Med tanke på ojämlikheten (13) och invarianten (22), säkerställer stoppregeln (21) att X t är en ε-suboptimal lösning till (6) när iterationen stannar. Dessutom säkerställer Theorem 1 att den beräknade lösningenX t är en nära-optimal rank-r approximation av X t vid varje tidpunkt t. Den totala lagringskostnaden är  och den skiss (Y, W ). På grund av antagandet om black-box (8) fullbordar algoritmen de enskilda vektorberäkningarna i (19) med arbetslagring (d + m + n). Ingen punkt under iterationen vi omedelbart en m × n matris! Aritmetiska kostnader är i samma ordning som standardversionen av CGM. SketchyCGM är en bevisligen korrekt metod för att beräkna en låggradig approximation av en lösning till (6). Andra teoretikern. Antag att itererar X t från CGM iteration (9)-(11) konvergera till en matris X cgm. LetX t vara rank-r rekonstruktion av X t produceras av SketchyCGM. I synnerhet om rank(X cgm ) ≤ r, då SketchyCGM alltid fungerar i det grundläggande fallet där varje lösning (6) har låg rank. Teorin 3. Antag att lösningen uppsättning S av problemet (6) innehåller endast matriser med rank r eller mindre. Då SketchyCGM uppnår E dist F (X t, S ) → 0. Antag att den optimala punkten av (6) är stabil i den meningen att värdet av den objektiva funktionen ökar när vi avviker från optimalitet. Sedan konvergerar SketchyCGM-skattningarna med kontrollerad hastighet. Teorin 4. Fix δ > 0 och v > 0. Antag att (unik) lösning X av (6) har rang(X ) ≤ r och Convex Low-Rank Matrix Optimering med optimal lagring Algoritm 1 SketchyCGM för modellproblem (6) Ingång: Data för (6); suboptimalitet ε; mål rank r Utgång: Rank-r ungefärlig lösningX = U  och V * av (6) i faktoriserad form för alla möjliga X. Då har vi felet bundet där C är krökningskonstanten [23, Eqn. (3)] av problemet (6). Se bilaga A för bevis på dessa resultat. Därefter presenterar vi en generalisering av problemet med hämtning av konvexa faser (5). Betrakta konvex mall Som tidigare, A : C n×n → C d är en linjär karta, och f : Det är lätt att anpassa SketchyCGM att hantera (24) i stället för (6). För att skissa den komplexa psd-matrisvariabeln följer vi den metod som beskrivs i [37, Sec. I punkt 7.3 ska följande stycke läggas till: Vi gör också små förändringar i SketchyCGM iteration. Ersätt beräkningen (19) med (λ t, u t ) = MinEig( A * ( ska f (z t ))); A (αu t u * t ), λ t ≤ 0 0, annars. MinEig returnerar det lägsta eigenvärdet λ t och en tillhörande eigenvekator u t av en konjugatsymmetrisk matris. Denna variant beter sig på samma sätt som SketchyCGM. I detta avsnitt visar vi att SketchyCGM är en praktisk algoritm för konvex matrisoptimering med låg rankning. Vi fokuserar på fashämtningsproblem eftersom de ger en dramatisk illustration av kraften i lagringsoptimal konvex optimering. Bilaga B innehåller ytterligare exempel, inklusive några matriskompletteringsproblem. Till att börja med visar vi att vår strategi för att lösa konvexa fashämtningsproblem (5) har bättre minnesskalning än andra konvexa optimeringsmetoder. Alla fem metoderna löser (24) på ett tillförlitligt sätt. Proximala metoder (PGM och AT) utför en fullständig eigen value nedbrytning av iterat vid varje steg, men de kan accelereras genom att adaptivt välja antalet eigenvectors att beräkna. Metoderna baserade på CGM behöver bara den översta eigenvectorn, så de utför mindre aritmetisk per iteration. För att jämföra lagringskostnaderna för de fem algoritmerna, låt oss överväga en syntetisk fas hämtning problem. Vi ritar en vektor x C n från den komplexa standard normalfördelningen. Sedan får vi d = 10n faslösa mätningar (3), korrumperade med oberoende Gaussiskt brus så att SNR är 20 dB. Mätvektorerna a i härrör från ett kodat diffraktionsmönster; se §B.3.2 för närmare information. Vi löser konvexa problem (5) med α lika med medelvärdet av mätningarna b i ; se [39, Sec. II) och förordning (EEG) nr 4064/89, i dess lydelse enligt rådets förordning (EEG) nr 4064/89 av den 21 december 1989 om tillämpningsföreskrifter för rådets förordning (EEG) nr 4064/89 om tillämpningsföreskrifter för rådets förordning (EEG) nr 4064/89 om tillämpningsföreskrifter för rådets förordning (EEG) nr 4064/89 om harmonisering av medlemsstaternas lagstiftning rörande omsättningsskatter, rådets förordning (EEG) nr 4064/89 om harmonisering av medlemsstaternas lagstiftning rörande omsättningsskatter, rådets förordning (EEG) nr 4064/89 om harmonisering av medlemsstaternas lagstiftning rörande omsättningsskatter och rådets förordning (EEG) nr 4064/89 om tillämpningsföreskrifter för rådets förordning (EEG) nr 4064/89 om harmonisering av medlemsstaternas lagstiftning rörande omsättningsskatter. Sedan beräknar vi en toppegenvector x av lösningen.
I REF presenterar författarna en ny metod för villkorad lutning som har ett lågt minnesavtryck för vissa fall av (1) såsom det välkända matriskompletteringsproblemet, men det finns ingen förbättring av konvergenshastigheten utöver standardmetoden.
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
{'venue': 'AISTATS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}