Complétion de Matrice à Partir de Quelques Entrées

Soit M une matrice de taille n × n de rang r, et supposons qu'un sous-ensemble E de ses entrées soit observé de manière uniformément aléatoire. Nous décrivons un algorithme efficace, que nous appelons OptSpace, qui reconstruit M à partir de |E| = O(rn) entrées observées avec une erreur quadratique moyenne relative de 1/2 RMSE ≤ C(ε) (nr/|E|) 1/2 avec une probabilité supérieure à 1 - 1/n³. De plus, si r = O(1) et M est suffisamment déstructuré, alors OptSpace la reconstruit exactement à partir de |E| = O(n log n) entrées avec une probabilité supérieure à 1 - 1/n³. Cela résout (dans le cas d'un rang borné) une question laissée ouverte par Candes et Recht et améliore les garanties pour leur algorithme de reconstruction. La complexité de notre algorithme est O(|E|r log n), ce qui ouvre la voie à son utilisation pour des ensembles de données massives. Dans le processus de preuve de ces affirmations, nous obtenons une généralisation d'un résultat célèbre de Friedman-Kahn-Szemerédi et Feige-Ofek sur le spectre des matrices aléatoires clairsemées.