MATRIX COMPLETION PAPERS

We distinguish two types of matrix completion: matrix completion when a subset of entries is observed, and matrix completion when a linear functional of the entire matrix is observed. SVT, and the papers below, deal with the first type; for an introduction to the latter type (which is in some sense an extension of compressed sensing), Guaranteed minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, by Recht, Fazel and Parrilo, is a good place to start.

Theory:

• Exact matrix completion via convex optimization by E. J. Candès and B. Recht (2008).
• Necessary and Sufficient Condtions for Success of the Nuclear Norm Heuristic for Rank Minimization, by B. Recht, W. Xu and B. Hassibi (2008). The extended technical report has full proofs.
• The power of convex relaxation: Near-optimal matrix completion, by E. Candès and T. Tao (2009).
• Matrix completion with noise, by E. J. Candès and Y. Plan (2009).

Algorithms:

• A singular value thresholding algorithm for matrix completion by J-F. Cai, E. J. Candès and Z. Shen (2008).
• Fixed point and Bregman iterative methods for matrix rank minimization by S. Ma, D. Goldfarb and L. Chen (2008).
• Interior-point method for nuclear norm approximation with application to system identification by Z. Lui and L. Vandenberghe (2008).
• Matrix Completion from a Few Entries, by R. Keshavan, A. Montanari, and S. Oh (2009).
• An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems by K. Toh and S. Yun (2009).
• Templates for First-Order Conic Solvers by S. Becker, E. Candès and M. Grant (2010). This generalizes and improves the approach taken in SVT.
• RTRMC : A Riemannian trust-region method for low-rank matrix completion by N. Boumal and P. Absil (2011).