Notions such as order, complexity, and dimensionality can often be expressed by means of the rank of an appropriate matrix. A matrix has low-rank if its rows or columns span a very low dimensional space. A low-rank matrix could correspond to a low-degree statistical model for a random process or the set of pairwise distances in a cloud of points.
Matrix completion is the problem where one tries to estimate a low-rank matrix from a sparse collection of measurements, such as the values of just a few entries of the matrix. To illustrate the practical importance of this problem, consider the task of inferring answers in a partially filled out survey in which questions are asked of a collection of individuals. We can form a matrix in which the rows index the individuals and the columns index the questions. When many questions are left unanswered, is it possible to make an educated guess about what the missing answers should be? If we assume that only a few factors contribute to an individual's tastes or preferences, we can use low-rank matrix estimation to infer the missing answers.
Although specific instances can often be solved with specialized algorithms, the general rank minimization problem is NP-hard. My collaborators and I have studied conditions when the minimum rank solution can be recovered by solving a simple optimization problems. We use probabilistic techniques to study average case behavior, and show that many of these hard problems can be solved with simple techniques in practice.
Relevant papers and reports
Guaranteed Minimum Rank Solutions to Linear Matrix Equations via Nuclear Norm Minimization. Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. SIAM Review. 52(3):471–501, 2010.
Exact Matrix Completion via Convex Optimization. Emmanuel Candès and Benjamin Recht. Foundations of Computational Mathematics. 9(6):717-–772, 2009. Communications of the ACM Research Highlight, 55(6):111-119, 2012.
Null space conditions and thresholds for rank minimization. Benjamin Recht, Weiyu Xu, and Babak Hassibi. Mathematical Programming, Series B. 127:175-–202, 2011. An early version appeared as
A Simpler Approach to Matrix Completion. Benjamin Recht. Journal of Machine Learning Research. 12:3413-—3430, 2011.
Low-rank Solutions of Linear Matrix Equations via Procrustes Flow. Stephen Tu, Ross Boczar, Mahdi Soltanolkotabi, and Benjamin Recht. Preprint, 2015.
Parallel Stochastic Gradient Algorithms for Large-Scale Matrix Completion. Benjamin Recht and Christopher Re. Mathematical Programming Computation. 5(2):201–226, 2013.
Practical Large-Scale Optimization for Max-Norm Regularization Jason Lee, Benjamin Recht, Ruslan Salakhutdinov, Nathan Srebro, and Joel A. Tropp. In Advances in Neural Information Processing Systems, 2010.
Online Identification and Tracking of Subspaces from Highly Incomplete Information. Laura Balzano, Robert Nowak, and Benjamin Recht. In /Proceedings of the 48th annual Allerton Conference on Communication, Control, and Computing’, 2010.
Efficient matrix completion for seismic data reconstruction. R. Kumar, C. Da Silva, O. Akalin, A.Y. Aravkin, H. Mansour, B. Recht, F.J. Herrmann. Geophysics. 80(5):V97–V114, 2015.
Fast methods for denoising matrix completion formulations, with applications to robust seismic data interpolation. Aleksandr Y. Aravkin, Rajiv Kumar, Hassan Mansour, Benjamin Recht, Felix J. Herrmann. SIAM Journal on Scientific Computing. 36(5):S237–S266, 2015