The Power of Convex Relaxation: Near-Optimal Matrix Completion
By E.J. Candes, Terence Tao. 2009
2,327 citations recorded by the source corpus.
This paper is concerned with the problem of recovering an unknown matrix from a small fraction of its entries. This is known as the matrix completion problem, and comes up in a great number of applications, including the famous Netflix Prize and other similar questions in collaborative filtering. In general, accurate recovery of a matrix from a small number of entries is impossible, but the knowledge that the unknown matrix has low rank radically changes this premise, making the search for solutions meaningful. This paper presents optimality results quantifying the minimum number of entries needed to recover a matrix of rank r exactly by any method whatsoever (the information theoretic limit). More importantly, the paper shows that, under certain incoherence assumptions on the singular vectors of the matrix, recovery is possible by solving a convenient convex program as soon as the number of entries is on the order of the information theoretic limit (up to logarithmic factors). This convex program simply finds, among all matrices consistent with the observed entries, that with minimum nuclear norm. As an example, we show that on the order of nr log(n) samples are needed to recover a random n x n matrix of rank r by any method, and to be sure, nuclear norm minimization succeeds as soon as the number of entries is of the form nr polylog(n).
Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Statistical Learning Theory, Mathematical Optimization
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Dacheng Tao
- Percy Liang
- Michael I. Jordan
- Mohit Bansal
- Sergey Levine
- Ruslan Salakhutdinov
- Quoc V. Le
In Computational Mechanics
- E.J. Candes
- Martin J. Wainwright
- Prateek Jain
- Wotao Yin
- Zhouchen Lin
- Justin K. Romberg
- René Vidal
- Yin Zhang
In Computer Networks and Communications
- Wotao Yin
- Prateek Jain
- Justin K. Romberg
- Richard Baraniuk
- Yonina C. Eldar
- Andrea Montanari
- Ohad Shamir
- Dacheng Tao
In Statistical Learning Theory
- Yuanzhi Li
- Prateek Jain
- Jason D. Lee
- Francis R. Bach
- Karim Lounici
- Robert Tibshirani
- Alexandre B. Tsybakov
- Tong Zhang
In Mathematical Optimization
- Prateek Jain
- Srinadh Bhojanapalli
- Moritz Hardt
- Jason D. Lee
- Sujay Sanghavi
- E.J. Candes
- Yuxin Chen
- Robert Tibshirani
Citations in the corpus
- Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “A natural approach to recover the ground truth matrix is to solve a weighted low-rank approximation problem where the weights are inversely proportional to the variance i the entries [Gadian, 1982, Wentzell et al., 1997].”
- Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, background): “The problem is to “complete” the matrix based on the observed entries, and has been dubbed the matrix completion problem (Candès and Recht, 2008; Candès and Tao, 2009; Rennie and Srebro, 2005).”
- Diverse Few-Shot Text Classification with Multiple Metrics (2018, methodology): “To address the aforementioned challenges, we propose a novel task clustering algorithm based on the theory of matrix completion (Candès and Tao, 2010).”
- Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, background): “More recently, Candès–Recht [22] and Candès– Tao [23] considered the problem of completing a low-rank matrix from a random sample of its entries.”
- Blind Deconvolution Using Convex Programming (2012, background): “When the observations are randomly chosen entries in the matrix, then subject to incoherence conditions on the singular vectors of the matrix being measured, the number of samples sufficient for recovery, again with high probability, is [23–26] L ≥ Const ·Rmax(K,N) log(max(K,N)).”
- Phase Retrieval via Matrix Completion (2011, background): “the conditions derived in the literature [13, 15, 64] that would guarantee a formal equivalence between the two programs.”
- Matrix Completion From any Given Set of Observations (2013, background): “One line of research [5, 6, 4] studies conditions under which Alg1(Tr) retrieves the matrix exactly 1.”
- Generalized Nonconvex Nonsmooth Low-Rank Minimization (2014, background): “It has been proved that under certain incoherence assumptions on the singular values of the matrix, solving the convex nuclear norm regularized problem leads to a near optimal low-rank solution [6].”
- Universal Matrix Completion (2014, methodology): “Using similar argument as above, Lemma now follows by using (5), (6), and the above given inequality.”
- Matrix recovery from quantized and corrupted measurements (2014, background): “In order to take into account the quantized nature of the available data, we jointly learn the underlying quantization bin boundaries and recover the low-rank matrix, while removing potential (sparse) corruptions.”
- Robust Matrix Completion and Corrupted Columns (2011, background): “…a high level, this follows a similar line as works in support recovery (Candès et al., 2006), low-rank matrix recovery and matrix completion papers, (Recht et al., 2010; Candès & Tao, 2010; Gross, 2009; Recht, 2009)) and matrix decomposition (Candès et al., 2009; Chandrasekaran et al., 2009).”
- A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion (2009, methodology): “Also plotted are the reconstruction rates obtained for the convex relaxation approach of [10] solved using the Singular Value Thresholding algorithm [7], the FPCA algorithm from [22] and ADMiRA [21].”
- Templates for convex cone problems with applications to sparse signal recovery (2010, background): “It has been shown [14,18,33] that an effective way of recovering the missing information from y and the model (1.”