Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit

Zhisu Zhu, Anthony Man-Cho So, Yinyu Ye

Motivated by the philosophy and phenomenal success of compressed sensing, the problem of reconstructing a matrix from a sampling of its entries has attracted much attention recentl…