Att minimera rangen av en matris som är föremål för affina begränsningar är ett grundläggande problem med många viktiga tillämpningar inom maskininlärning och statistik. I detta dokument föreslår vi en enkel och snabb algoritm SVP (Singular Value Projection) för rankminimering med affina begränsningar (ARMP) och visar att SVP återvinner den lägsta ranklösningen för affina begränsningar som uppfyller den begränsade isometry egenskapen. Vi visar robusthet i vår metod för buller med en stark geometrisk konvergens även för bullriga mätningar. Våra resultat förbättras vid ett genombrott nyligen av Recht, Fazel och Parillo [RFP07] och Lee och Bresler [LB09a] på tre viktiga sätt: 1) vår metod (SVP) är betydligt enklare att analysera och lättare att genomföra, 2) vi ger återvinningsgarantier enligt strikt svagare isometri antaganden 3) vi ger geometriska konvergensgarantier för SVP och, vilket visats empiriskt, SVP är betydligt snabbare på verkliga och syntetiska problem. Dessutom tar vi upp det praktiskt taget viktiga problemet med matriskomplettering på låg nivå, vilket kan ses som ett specialfall av ARMP. De affina begränsningar som definierar matris-kompletion problemet inte lyda den begränsade isometry egenskapen i allmänhet. Vi visar empiriskt att vår algoritm återvinner lågvärdiga inkonsekventa matriser från ett nästan optimalt antal enhetligt provade poster. Vi gör partiella framsteg mot att bevisa exakt återhämtning och ger viss intuition för prestanda SVP tillämpas på matrisen slutföra genom att visa en mer begränsad isometry egenskap. Vår algoritm överträffar befintliga metoder, såsom de av [RFP07, CR08, CT09, CCS08, KOM09], för ARMP och matris-kompletering problem av en storleksordning och är också betydligt mer robust mot buller.
REF minimerade rankminimeringen med algoritmen Singular value project (SVP).
Guaranteed Rank Minimization via Singular Value Projection
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}