Abstract-Vi presenterar nya tekniker för att analysera problemet med låg-rank matris återhämtning. Metoderna är både betydligt enklare och mer generella än tidigare metoder. Det visas att en okänd n × n matris av rang r effektivt kan rekonstrueras från endast O (nrν ln 2 n) slumpmässigt provade expansionskoefficienter med avseende på varje given matrisbas. Antalet v kvantifierar "graden av inkonsekvens" mellan den okända matrisen och basen. Befintligt arbete koncentrerades främst på problemet med "matriskomplettering" där man strävar efter att återställa en låg-rankad matris från slumpmässigt utvalda matriselement. Vårt resultat omfattar denna situation som ett specialfall. Beviset består av en rad relativt elementära steg, som står i kontrast till de mycket involverade metoder som tidigare använts för att uppnå jämförbara resultat. I fall där gränser hade varit kända tidigare, våra uppskattningar är något snävare. Vi diskuterar operatörsbaser som är osammanhängande med alla lågrankade matriser samtidigt. För dessa baser, visar vi att O (nrν ln n) slumpmässigt provade expansionskoefficienter räcker för att återställa någon låg rank matris med hög sannolikhet. Den senare är bunden till multiplikativa konstanter.
Förutom matris komplettering, Gross analyserade problemet med att effektivt återvinna en låg-rank matris från en bråkdel av observationer i någon bas REF.
Recovering low-rank matrices from few coefficients in any basis
{'venue': 'IEEE Trans. on Information Theory, vol. 57, pages 1548 - 1566 (2011)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}