Matrix Completion from a Few Entries

Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh

Let M be a random (alpha n) x n matrix of rank r<<n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M…