Matrix Completion from $O(n)$ Samples in Linear Time

David Gamarnik, Quan Li, Hongyi Zhang

We consider the problem of reconstructing a rank-$k$ $n\times n$ matrix $M$ from a sampling of its entries. Under a certain incoherence assumption on $M$ and for the case when bot…