Låt M vara en n2n matris av rank r,andassume att en jämnt slumpmässig delmängd E av dess poster observeras. Vi beskriver en effektiv algoritm, som vi kallar OPTSPACE, som rekonstruerar M från jEj = O(rn) observerade poster med relativ rot genomsnittliga kvadratfel RMSE C() nr jEj 1=2 med sannolikhet större än 1 0 1=n 3. Vidare, om r = O(1) och M är tillräckligt ostrukturerad, då OPTSPACE rekonstruerar det exakt från jEj = O(nlogn) poster med sannolikhet större än 1 0 1=n 3. Detta avgör (i fallet med begränsad rang) en fråga som lämnats öppen av Candès och Recht och förbättrar garantierna för deras återuppbyggnadsalgoritm. Komplexiteten i vår algoritm är O(jEjr log n), som öppnar vägen till dess användning för massiva datamängder. I processen att bevisa dessa uttalanden, får vi en generalisering av ett firat resultat av Friedman-Kahn-Szemerédi och Feige-Ofek på spektrumet av glesa slumpmässiga matriser.
För en begränsad rank r = O(1) är prestanda bundet av OPTSPACE ordning optimal REF.
Matrix Completion From a Few Entries
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}