Learning Low Rank Matrices from O(n) Entries

Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh

How many random entries of an n by m, rank r matrix are necessary to reconstruct the matrix within an accuracy d? We address this question in the case of a random matrix with bound…