Matrix Completion from Noisy Entries

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

744 citations recorded by the source corpus.

Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the 'Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced in [1], based on a combination of spectral techniques and manifold optimization, that we call here OPTSPACE. We prove performance guarantees that are order-optimal in a number of circumstances.

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “Comparison with related work on matrix completion: (1) (Candes & Plan, 2010); (2) (Keshavan et al., 2009); (3) (Bhojanapalli & Jain, 2014); (4) (Hardt, 2014).”
Exact Matrix Completion via Convex Optimization (2008, background): “The work in Keshavan et al.(22) gives near-optimal bounds provided the unknown matrix obeys additional assumptions which say that the singular values are all about the same size.”
Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, methodology): “Moving away from the phase retrieval problem, we would like to mention some very interesting work on the matrix completion problem using non-convex schemes by Montanari and coauthors [38]–[40], see also [2], [6], [32], [37], [41], [51], [52].”
Estimation of high-dimensional low-rank matrices (2009, background): “…same setting in the presence of noise, proposed estimators ˆ A of A ∗ and evaluated their Frobenius norm ˆ A − A ∗ F . k k The better bounds are in Keshavan, Montanari and Oh (2009) who suggest ˆ A such that for A ∗ ∈ R m × T and T = αm with α > 1 the squared error k ˆ A − A ∗ k 2 F is of the…”
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 ”
Nuclear norm penalization and optimal rates for noisy low rank matrix completion (2010, background): “However, the construction of the estimator in [15] requires the exact knowledge of rank(A0) and the upper bound on the Frobenius error obtained in [15] is suboptimal (see the details in Section 3).”
Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements (2011, background): “Several different algorithms have been proposed , with many drawing their roots from standard compressive sensing techniques [3], [4], [6], [8], [9], [11], [14]–[16].”
Local Low-Rank Matrix Approximation (2013, positive): “Recent algorithmic progress in matrix completion was achieved by Toh & Yun (2010); Keshavan et al. (2010).”
Generalized Low Rank Models (2014, background): “when the initial values of X and Y are chosen carefully [74, 76, 73, 66, 58, 55, 59, 140].”
A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion (2009, methodology): “More recently, a bound on the RMSE achieved by the OptSpace algorithm with noisy observations was obtained in [20].”
Fast Differentially Private Matrix Factorization (2015, methodology): “This procedure is the underlying gem that allows OptSpace (the very first provable matrix factorization based low-rank matrix completion method) [12] to work.”
Manopt, a matlab toolbox for optimization on manifolds (2013, background): “…the Grassmann manifold proves useful in low-rank matrix completion, where it is observed that if one knows the column space spanned by the sought matrix, then completing the matrix according to a least squares criterion is easy (Keshavan et al. , 2010; Boumal & Absil, 2011; Balzano et al. , 2010).”
Matrix Completion, Counterfactuals, and Factor Analysis of Missing Data (2019, background): “ if a matrix is incoherent. Since 8See for example, Candes and Recht (2011), Candes and Tao (2010, Theorem 1.7), Candes and Plan (2010, Theorem 2, p.929), Keshevan et al. (2010, Theorem 1.2, p.2982), Keshavan et al. (2010, p.2061), Candes et al. (2011) Jain et al. (2013) and Hardt (2014) put restric”
Robust Recovery of Subspace Structures by Low-Rank Representation (2010, methodology): “ubspace methods have been gaining much attention in recent years. For example, the widely used Principal Component Analysis (PCA) method and the recently established matrix competition [7], [8], [9], [10] methods are essentially based on the hypothesis that the data is approximately drawn from a low”
Low-rank tensor completion by Riemannian optimization (2014, neutral): “[6, 13].”