Exact Matrix Completion via Convex Optimization
By E.J. Candes, B. Recht. 2008
6,366 citations recorded by the source corpus.
We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen?We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys $$m\ge C\,n^{1.2}r\log n$$ for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.
Subfields: Biomedical Engineering, Computational Mechanics, Mathematical Optimization, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Biomedical Engineering
- E.J. Candes
- Prateek Jain
- Lei Zhang
- Stephen P. Boyd
- Xiaoming Yuan
- B. Recht
- Sujay Sanghavi
- M. Soltanolkotabi
In Computational Mechanics
- Martin J. Wainwright
- E.J. Candes
- Francis R. Bach
- Wotao Yin
- Prateek Jain
- Peter Richtárik
- Lei Zhang
- Zhouchen Lin
In Mathematical Optimization
- Prateek Jain
- Zhi-Quan Tom Luo
- E.J. Candes
- Srinadh Bhojanapalli
- Jason D. Lee
- Martin J. Wainwright
- Justin K. Romberg
- Stephen J. Wright
In Signal Processing
- Martin J. Wainwright
- E.J. Candes
- Prateek Jain
- Sahand N. Negahban
- Wotao Yin
- Bart Vandereycken
- Sewoong Oh
- Srinadh Bhojanapalli
Citations in the corpus
- Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (2011, background): “Such problems arise in collaborative filtering, Euclidean distance estimation, and clustering [8,17,23].”
- Machine Learning Methods That Economists Should Know About (2019, neutral): “See Candès and Recht [2009], Mazumder et al.”
- Data Poisoning Attacks on Factorization-Based Collaborative Filtering (2016, methodology): “(2) and (3) provably approximate the true underlying data matrix M under certain conditions [6, 2].”
- Principal Components and Regularized Estimation of Factor Models (2017, background): “Candes and Recht (2011) shows Z can be recovered with high probability if the number of observed entries satisfies a lower bound, and that the unobserved entries are missing uniformly at random.”
- Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, background): “Recently Candès and Recht (2008), Candès and Tao (2009), and Keshavan et al.”
- Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks (2017, background): “Cand ` es and Recht 2009 proved that the (cid:96) 1 relaxation of the SVD lead to solutions that recover almost exactly the original low-rank matrix.”
- Geometric Deep Learning: Going beyond Euclidean data (2016, methodology): “Mathematically, a recommendation method can be posed as a matrix completion problem [92], where columns and rows represent users”
- Introduction to Online Convex Optimization (2016, background): “The matrix completion model has been extremely popular since its inception in the context of recommendation systems (103; 88; 94; 70; 26; 101).”
- Geometric median and robust estimation in Banach spaces (2013, background): “For instance, it would be interesting to obtain an estimator in the low-rank matrix completion framework [11,24] that admits strong performance guarantees for the heavy-tailed noise model.”
- A Singular Value Thresholding Algorithm for Matrix Completion (2008, methodology): “This more general formulation is considered in [16] and [56] as an extension of the matrix completion problem.”
- GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “Such a notation has been used in compressed sensing [3], matrix completion [2], and randomized linear algebra [6, 40, 39].”
- Implicit Regularization in Matrix Factorization (2017, background): “The emerging story is that gradient descent biases us to a low nuclear norm solution, and we already know how having low nuclear norm can ensure generalization [17, 6] and minimizing the nuclear norm ensures reconstruction [15, 5].”
- The importance of better models in stochastic optimization (2019, background): “♦ Example 2 (matrix completion): In the matrix completion problem (25), which arises (for example) in the design of recommendation systems, we have a matrix M∈Rm×n with decomposition M = X?Y ? for X? ∈R m×r and Y? ∈Rn×r .”
- Guaranteed Matrix Completion via Non-Convex Factorization (2014, methodology): “A major difference of this paper from the existing results is that we do not need resampling (i.e., using independent samples at each iteration) in either the algorithm or its analysis.”
- Guaranteed Rank Minimization via Singular Value Projection (2009, methodology): “The above notion of incoherence is similar to that introduce by Candes and Recht [6] and also used by [7, 14].”