Matrix Completion With Noise

By E.J. Candes, Yaniv Plan. 2009

1,855 citations recorded by the source corpus.

On the heels of compressed sensing, a new field has very recently emerged. This field addresses a broad range of problems of significant practical interest, namely, the recovery of a data matrix from what appears to be incomplete, and perhaps even corrupted, information. In its simplest form, the problem is to recover a matrix from a small sample of its entries. It comes up in many areas of science and engineering, including collaborative filtering, machine learning, control, remote sensing, and computer vision, to name a few. This paper surveys the novel literature on matrix completion, which shows that under some suitable conditions, one can recover an unknown low-rank matrix from a nearly minimal set of entries by solving a simple convex optimization problem, namely, nuclear-norm minimization subject to data constraints. Further, this paper introduces novel results showing that matrix completion is provably accurate even when the few observed entries are corrupted with a small amount of noise. A typical result is that one can recover an unknown matrix of low rank from just about log noisy samples with an error that is proportional to the noise level. We present numerical results that complement our quantitative analysis and show that, in practice, nuclear-norm minimization accurately fills in the many missing entries of large low-rank matrices from just a few noisy samples. Some analogies between matrix completion and compressed sensing are discussed throughout.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Statistical Learning Theory, 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 Computer Vision and Pattern Recognition

In Statistical Learning Theory

In Signal Processing

Citations in the corpus

A Singular Value Thresholding Algorithm for Matrix Completion (2008, background): “In fact, very recent work [20] performed after the original submission of this paper suggests that even with considerable side information about the unknown matrix, one would not be able to do much better.”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “This result was later generalized to noisy matrix completion, whereby the optimization formulation (2) is adopted [7].”
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm (2012, methodology): “…and Applied Mathematics, Rice University, Houston, TX 77005, USA e-mail: wotao.yin@rice.edu Y. Zhang e-mail: yzhang@rice.edu Keywords Matrix completion · Alternating minimization · Nonlinear GS method · Nonlinear SOR method Mathematics Subject Classification 65K05 · 90C06 · 93C41 · 68Q32”
Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads (2020, background): “Matrix completion enables sparse low rank matrices to be reconstructed with low error [17,43].”
Sparse Bayesian Methods for Low-Rank Matrix Estimation (2011, background): “Note that a matrix of size of rank depends upon degrees of freedom (df), and the oversampling degrees of freedom (osdf) is defined as with the number of measurements [23].”
Guaranteed Rank Minimization via Singular Value Projection (2009, background): “Also, though minimizing the trace-norm approximates the low-rank solution even in the presence of noise (see [CP09], [LB09b] for instance), noise poses considerable computational challenges for trace-norm optimization.”
Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization (2013, background): “Recent progress in matrix completion shows that, under some general constraints, nuclear norm minimization can recover this incomplete matrix from sufficient observed entries [1], [15], [16], [2].”
Robust Matrix Completion via Joint Schatten p-Norm and lp-Norm Minimization (2012, result): “1), which is consistent with (or even more accurate than) the theoretical results established in [19] and further confirm the correctness of our method.”
Colour of turbulence (2016, methodology): “Thus, instead, we employ nuclear norm regularization as a surrogate for rank minimization (Fazel 2002; Candès & Recht 2009; Candès & Plan 2010; Recht, Fazel & Parrilo 2010).”
Nonparametric Bayesian Dictionary Learning for Analysis of Noisy and Incomplete Images (2011, methodology): “Therefore, this construction is closely linked to the optimization approach advocated for near-low-rank matrix completion [7], which also uses a Frobenius”
Optimum Co-Design for Spectrum Sharing between Matrix Completion Based MIMO Radars and a MIMO Communication System (2015, methodology): “This means that Ω is either a uniformly random sub-sampling matrix [36], or a matrix with a large spectral gap [34].”
Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization (2011, methodology): “Our proof technique is adapted from [29] (see also [30]) but in a different context.”
Recovering Low-Rank Matrices From Few Coefficients in Any Basis (2009, methodology): “The basic intuition underlying our results differs little from previous approaches [1]–[4].”
Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm (2015, background): “The first two aim to examine the convergence behavior of IRNN for the matrix completion problem [45] on both synthetic data and real images.”
Low-Rank Matrix Completion by Riemannian Optimization (2012, result): “Related work has been done by [14, 16, 27, 28], which in particular also establish similar recovery results for the robust formulation (1.”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, result): “Similar results can also be established that guarantee approximate recovery in the case of noisy observations and approximately low-rank matrices with the amount of recovery error being naturally determined by the amount of noise and degree of approximation error [27,56,57,79,81,83,84,105,119].”