Matrix Completion With Noise

Abstract

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.

11 pages, 4 figures, 1 table

References in corpus (3)

• A Singular Value Thresholding Algorithm for Matrix Completion
• Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization
• Uniqueness of Low-Rank Matrix Completion by Rigidity Theory

Cited by in corpus (28)

• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Matrix Completion from Noisy Entries
• Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard
• Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices
• Guaranteed Rank Minimization via Singular Value Projection
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
• Stable Principal Component Pursuit
• Bayesian methods for low-rank matrix estimation: short survey and theoretical study
• Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions
• Sharp oracle inequalities for the prediction of a high-dimensional matrix
• Matrix Completion from $O(n)$ Samples in Linear Time
• Matrix factorization for multivariate time series analysis
• Weighted Singular Value Thresholding and its Application to Background Estimation
• Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison
• Optimal spectral norm rates for noisy low-rank matrix completion
• Regularization for Matrix Completion
• Continuous-variable quantum compressed sensing
• Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
• A novel low-rank matrix completion approach to estimate missing entries in Euclidean distance matrices
• A Stochastic Model for Collaborative Recommendation
• A Geometric Approach to Low-Rank Matrix Completion
• Subspace Segmentation by Successive Approximations: A Method for Low-Rank and High-Rank Data with Missing Entries
• Information Theoretic Bounds for Low-Rank Matrix Completion
• The CP-matrix completion problem
• Increasing Energy Efficiency in Sensor Networks: Blue Noise Sampling and Non-Convex Matrix Completion
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Estimating Traffic and Anomaly Maps via Network Tomography
• Accurate low-rank matrix recovery from a small number of linear measurements