Matrix completion from a few entries

By Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh. 2009

1,292 citations recorded by the source corpus.

Let M be an nα × n matrix of rank r ≪ n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(r n) observed entries with relative root mean square error RMSE ≤ C(α) (nr/|E|)<sup>1/2</sup>. Further, if r = O(1) and M is sufficiently unstructured, then it can be reconstructed exactly from |E| = O(n log n) entries. This settles (in the case of bounded rank) a question left open by Candès and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log n), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemerédi and Feige-Ofek on the spectrum of sparse random matrices.

Subfields: Computational Mechanics, Statistics and Probability, Optimization & Training, 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 Computational Mechanics

In Statistics and Probability

In Optimization & Training

In Signal Processing

Citations in the corpus

Initialization and Regularization of Factorized Neural Layers (2021, background): “Outside deep learning, spectral methods have also been shown to yield better initializations for certain matrix and tensor problems (Keshavan et al., 2010; Chi et al., 2019; Cai et al., 2019).”
Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, background): “OPTSPACE–reconstruction algorithm by Keshavan et al. (2009);”
The landscape of empirical risk for nonconvex losses (2016, background): “elihood problem requires to minimize1 Rb n(θ) ≡ − 1 n Xn i=1 log Xk a=1 paφd zi−θa ! , (6) with respect to the cluster centers θ= (θ1,...,θk) ∈ Rd×k. Other examples include low-rank matrix completion [KOM09], phase retrieval [SQW16], tensor estimation problems [MR14], and so on. M-estimation with no”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “This is achieved in three steps: (i) study the local geometry of the fully observed objective (cid:4) M − XY T (cid:4) 2 F ; (ii) study the local geometry of the matrix completion objective (cid:4) P (cid:2) ( M − XY T ) 2 F ; (iii) study the local geometry of a regularized objective.”
Streaming PCA and Subspace Tracking: The Missing Data Case (2018, methodology): “the low-rank matrix completion problem [7], [71]–[74]), the only results in the streaming case with missing data are local convergence results for GROUSE and the work of [75], where the authors consider recovering a low-rank positive semidefinite matrix observed with missing data using stochastic gr”
Stability of matrix factorization for collaborative filtering (2012, methodology): “We recall similar RMSE bounds for StableMC of Can-des & Plan (2010) and OptSpace of Keshavan et al. (2010a): OptSpace: Albeit the fact that these bounds are for diﬀerent algorithms and under diﬀerent assumptions (see Table 1 for details), it is still interesting to compare the re-sults with Theorem ”
Scaled Gradients on Grassmann Manifolds for Matrix Completion (2012, methodology): “The readers are referred to [1, 11] for details on optimization frameworks on matrix manifolds.”
A Novel Sparse Compositional Technique Reveals Microbial Perturbations (2019, background): “It has been shown to be quite robust to noise in low-rank data sets (44).”
1-Bit Matrix Completion (2012, background): “…have a relatively long history, recent advances in the closely related ﬁeld of compressed sensing [13, 21, 23] have enabled a burst of progress in the last few years, and we now have a strong base of theoretical results concerning matrix completion [15–17, 25, 30, 36, 37, 39–42, 49, 55, 56].”
Robust principal component analysis? (2009, methodology): “The last year or two have seen the rapid development of a scientiﬁc literature concerned with the matrix completion problem introduced in [8], see also [7,10,22,23,43] and the references therein.”
Fixed point and Bregman iterative methods for matrix rank minimization (2009, result): “A similar result was shown by Keshavan et al. [ 26 ].”
Non-convex Optimization for Machine Learning (2017, methodology): “We point the reader to [Recht, 2011] and [Keshavan et al., 2010] for a more precise argument analyzing the initialization step in the general rank-r case.”
Gradient Descent Converges to Minimizers (2016, background): “We remark that the strict saddle assumption is necessary in the worst case, due to hardness results regarding testing the local optimality of functions whose Hessians are highly degenerate at criticalpoints (e.g, quartic polynomials) [19].”
Recommendation systems: Principles, methods and evaluation (2015, methodology): “[64] used SVD technique in an OptSpace algorithm to deal with matrix completion problem.”