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

David Gamarnik, Quan Li, Hongyi Zhang

Browse the full COLT paper archive.