Source-linked AI summary
Matrix Completion With Noise
Emmanuel J. Candes, Yaniv Plan
TL;DR
The paper addresses recovery of missing entries in low-rank matrices from limited and potentially noisy observations, a problem arising across several applications. It surveys nuclear-norm minimization for exact completion, develops results for noisy completion, and complements the analysis with numerical experiments. The supported results show that nuclear-norm minimization can recover all entries without error in a stated high-probability setting, while the paper also analyzes noisy recovery.
Problem
Matrix completion asks whether missing entries of a low-rank data matrix can be recovered from only a subset of entries, motivated by applications including filtering, control, sensing, and localization.
Method
The paper surveys and analyzes nuclear-norm minimization as a convex approach to low-rank matrix completion, including geometric and dual-certificate arguments.
Results
Nuclear-norm minimization recovers all entries of the unknown matrix with no error in a stated high-probability exact-completion result.
Takeaways & Limitations
Low-rank matrix completion provides a common framework for inferring unobserved data in recommendation, system identification, remote sensing, and geometric localization.
Abstract
from arXiv · showhide
On the heels of compressed sensing, a remarkable 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, and 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 n x n matrix of low rank r from just about nr log^2 n noisy samples with an error which is proportional to the noise level. We present numerical results which 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.
I. INTRODUCTION
Matrix completion asks whether missing entries in low-rank data matrices can be recovered accurately from limited observations. The paper develops this problem across applications, studies noiseless and noisy settings, and uses nuclear-norm minimization as its central framework.
- Problem: Matrix completion recovers missing entries of a data matrix when the unknown matrix is low rank or approximately low rank.The paper presents this as the matrix analogue of sparse signal recovery in compressed sensing.
- Applications: Collaborative filtering models unseen movie, music, and literary preferences through an approximately low-rank user-item matrix.Only a few latent factors typically contribute to an individual’s tastes or preferences.
- Applications: System identification casts recovery of state dimension and dynamics from input-output data as a low-rank matrix recovery problem.The recovered quantities include the model order, system matrices, and initial state.
- Applications: Partial distance measurements in sensor networks form a matrix completion problem, with rank two for planar locations and rank three for spatial locations.The completed distance matrix supports reliable estimation of sensor locations.
- Applications: Partial covariance measurements in remote sensing can be completed because the signal covariance matrix has low rank relative to the number of sensors.Its rank equals the number of incident waves, which is usually much smaller than the sensor count.
- Paper scope: The paper studies exact recovery, recovery under noisy observations, and numerical performance using matrix norms and nuclear-norm minimization.Its notation includes spectral, Frobenius, and nuclear norms, alongside linear operators and positive-semidefinite ordering.
II. EXACT MATRIX COMPLETION
Exact matrix completion seeks to recover a low-rank matrix from sampled entries using nuclear-norm minimization, under sampling and incoherence conditions. With nearly minimal samples, this convex program can recover all entries exactly with high probability.
- Problem: Matrix completion infers an unknown matrix from sampled entries represented by the sampling operator PΩ(M).The entries are sampled from the complete set [n1] × [n2].
- Incoherence: Extremely sparse singular vectors can make exact completion impossible, requiring observation of every entry in an affected row or column.The paper uses a rank-one example concentrated in the first row to illustrate this obstruction.
- Method: Nuclear-norm minimization is used as a tractable convex relaxation of NP-hard rank minimization.The nuclear norm is characterized through semidefinite programming and is described as the tightest convex relaxation of rank minimization.
- Guarantees: O(n log^2 n) samples suffice for fixed-rank incoherent matrices, yielding exact recovery with probability at least 1 − n^-3.The result is within logarithmic factors of the information-theoretic sampling limit.
- Sampling: r(n1 + n2 − r) degrees of freedom explain why low-rank matrices can be subsampled, while random sampling must also cover every row and column.Missing an entire row or column prevents recovery, even for a rank-one matrix.
A. Geometry and dual certificates
The paper develops dual-certificate conditions for exact nuclear-norm matrix completion, linking geometric tangency and operator injectivity to uniqueness. These conditions also provide the foundation for stability under noise.
- Geometry and dual certificates: Space limitations prevent a full proof of Theorem 2, so the paper instead details sufficient and almost necessary conditions for uniqueness.These conditions are used to establish stability results.
- Geometry and dual certificates: Exact recovery occurs when the feasible set is tangent to the nuclear ball at the unknown matrix.Figure 1 illustrates the nuclear ball and feasible set geometrically.
- Geometry and dual certificates: A dual certificate is supported on the observed entries, matches the tangent-space sign matrix, and has complementary spectral norm at most one.This certificate supplies the subgradient structure needed for nuclear-norm optimality.
- Geometry and dual certificates: A dual certificate with complementary norm below one and an injective sampling restriction makes the unknown matrix the unique nuclear-norm minimizer.Any feasible perturbation outside the tangent space increases the nuclear norm, while injectivity eliminates nonzero tangent-space perturbations.
- Geometry and dual certificates: Under the theorem assumptions, a dual certificate and a near-isometric tangent-space sampling operator establish exact recovery and support robustness to noise.The sampling map’s injectivity verifies the sufficient conditions for uniqueness.
III. STABLE MATRIX COMPLETION
The stable-completion analysis models observed entries as noisy samples and reconstructs the matrix by minimum nuclear norm. Under the same structural conditions supporting noiseless recovery, the reconstruction error scales with the noise level, despite the absence of RIP.
- Stable recovery: Minimum nuclear norm among matrices consistent with the noisy data defines the proposed semidefinite-program reconstruction.The paper denotes the solution by M̂ and states that this reconstruction is accurate.
- Stable recovery: Under a dual-certificate bound and tangent-space sampling condition, the estimator M̂ obeys the theorem’s error bound.The stated conditions hold with very large probability under the noiseless-recovery assumptions.
- Stable recovery: The error is proportional to the noise level δ, so small perturbations yield small reconstruction error whenever perfect noiseless recovery occurs.Improving the conditions for noiseless recovery consequently improves recovery from noisy samples.
- RIP-less setting: Matrix completion lacks the restricted isometry property because an unobserved rank-one matrix can lie entirely in the sampling operator’s null space.The paper presents the resulting stability theorem as a significant novelty for this RIP-less setting.
- RIP-less setting: RIP-based estimates could be better by a factor proportional to 1/min(n1, n2), leaving the sharpness of RIP-less matrix-completion estimates open.The paper notes this comparison as an unresolved question.
- RIP-less setting: The methods also apply to sparse signal recovery problems in which the restricted isometry property does not hold.
A. Proof of Theorem 7
The proof of Theorem 7 begins by controlling the observed and unobserved components of the estimation error. Feasibility and the noise bound provide the tube constraint, while the nuclear-norm comparison provides the cone constraint.
- A. Proof of Theorem 7: Because M is feasible, the estimator error satisfies the cone constraint from nuclear-norm minimality.
- A. Proof of Theorem 7: The triangle inequality yields the tube constraint ∥PΩ(M̂ − M)∥F ≤ ∥PΩ(M̂ − Y)∥F + ∥PΩ(Y − M)∥F.
- A. Proof of Theorem 7: Writing M̂ = M + H and splitting H into observed and unobserved parts reduces the proof to bounding the unobserved component.The observed component is already bounded by ∥HΩ∥F ≤ 2δ.
F , (III.7)
The remaining proof bounds the tangent and orthogonal components of the unobserved error using dual-certificate inequalities, norm domination, and the sampling operator’s lower bound. Combining these estimates yields Theorem 7.
- F , (III.7): The proof bounds the second term using a dual certificate whose complementary spectral norm is at most 1/2.
- F , (III.7): Nuclear-norm domination of the Frobenius norm controls the orthogonal component of the unobserved error.Cauchy–Schwarz and the tube constraint complete this bound.
- F , (III.7): The lower bound PT PΩ PT ⪰ p/2 I is used to control the tangent component of the error.The proof also uses the projector identities for PT and the decomposition of the unobserved component.
- F , (III.7): Combining the final inequalities with the earlier estimate establishes the theorem’s error bound.
B. Comparison with an oracle
The section compares noisy matrix completion with oracle least-squares procedures and identifies the attainable error scale under bounded noise. The oracle uses subspace information unavailable to the standard method, providing a benchmark and revealing a √n analysis gap.
- Oracle construction: The least-squares oracle requires the sampling operator A∗A to be invertible, as ensured under the section’s hypotheses.The solution is formed by applying the inverse sampling operator to the observed data projected onto the relevant tangent space.
- Accuracy benchmark: The paper’s adversarial-noise analysis loses a factor of √n relative to an optimal oracle bound.This quantifies the gap between the analyzed recovery guarantee and the best accuracy achievable with oracle assistance.
- Oracle construction: The oracle is given the tangent space or row space and fits the unknown matrix from observed entries by least squares.A stronger oracle reveals the row space and rank, reducing recovery to fitting the unknown coefficients in that space.
- Accuracy benchmark: p^-1/2δ is the best root-mean squared error scale when the observed noise satisfies ∥PΩ(Z)∥F ≤δ.The stronger oracle also achieves this scale, establishing a lower bound on what recovery can hope to attain under the stated noise constraint.
- Accuracy benchmark: For stochastic white noise, the oracle error adapts to rank and improves when the rank is smaller.The comparison is especially favorable when nr is much smaller than the number of observations m.
IV. NUMERICAL EXPERIMENTS
The experiments test regularized nuclear-norm recovery on noisy, randomly sampled low-rank matrices and on an approximately low-rank weather-temperature matrix. Across these settings, the method recovers missing entries and can denoise observed ones, with performance compared against oracle benchmarks.
- Experimental setup: The simulations vary matrix dimension n, rank r, and observed fraction p, averaging errors over 20 trials for generated rank-r matrices.The observations are randomly sampled and corrupted by independent Gaussian noise with σ = 1.
- Experimental setup: The regularized nuclear-norm problem is solved with the FPC algorithm, using a parameter µ selected from a soft-thresholding heuristic.For square matrices, the proposed choice is µ = √2npσ; a rectangular-matrix analogue is also given.
- Oracle comparison: The recovery RMS error is compared with least-squares oracle error and estimated oracle error across varying n, p, and r.The plotted oracle errors are multiplied by 1.68 to match the observed scaling in the experiments.
- Real-world example: 0.166 relative error is obtained on a 366 × 1472 weather-temperature matrix using 30% observations, versus 0.121 for its best rank-two approximation.The experiment concerns an approximately low-rank matrix rather than an exactly low-rank one.
V. DISCUSSION
The discussion places matrix completion within an emerging research area connected to compressed sensing and identifies both theoretical and computational directions. It emphasizes open questions about general measurements and scalable optimization.
- Discussion: The paper characterizes low-rank matrix recovery as a young field with many interesting and open questions.Its growth is presented in relation to the recent development of compressed sensing.
- Discussion: The choice of rank-two approximation in the weather example is acknowledged as somewhat arbitrary; the best rank-ten approximation has relative error 0.081.This provides a different approximation boundary for the same approximately low-rank matrix.
- Open problems: At the information-theoretic level, the paper highlights recovery from general linear functionals A(M) = b as an open direction.It cites Gaussian linear measurements as an early result in this broader recovery setting.
- Open problems: At the computational level, scalable methods for nuclear-norm minimization remain needed for problems with millions or billions of unknowns.Existing algorithms are described as impressive in some situations but insufficient to resolve the largest computational challenges.