A Simpler Approach to Matrix Completion

By B. Recht. 2009

1,077 citations recorded by the source corpus.

This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low-rank matrix. These results improve on prior work by Candes and Recht (2009), Candes and Tao (2009), and Keshavan et al. (2009). The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.

Subfields: Artificial Intelligence, Computational Mechanics, Representation & Self-Supervised Learning, 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 Artificial Intelligence

In Computational Mechanics

In Representation & Self-Supervised Learning

In Signal Processing

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “( A3 ) Weight is not degenerate : Let D i = Diag ( W i ) , i.e., D i is a diagonal matrix whose diagonal entries are the i -th row of W .”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, background): “We have encountered these issues in a wide range of problems from computational mathematics: smoothed analysis of Gaussian elimination [51]; semidefinite relaxation and rounding of quadratic maximization problems [38, 50]; construction of maps for dimensionality reduction [1]; matrix approximation b”
Excess risk bounds for multitask learning with trace norm regularization (2012, methodology): “A linear map A : H → H is called an operator and self-adjoint if A ∗ = A and nonnegative (or positive) if it is self-adjoint and h Ax, x i ≥ 0 (or Ax, x > 0) for all x ∈ H , x = 0, in which case we write A 0 (or A ≻ 0). the operators h i 6 (cid:23) We use ” ” to denote order induced by the cone of…”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, methodology): “…unconstrained problem min On the theoretical side, it has been shown that given a rank-r matrix M satisfying an incoherence condition, solving (1) will exactly reconstruct M with high probability provided that O ( r ( m + n ) log 2 ( m + n )) entries are uniformly randomly revealed [4]–[7].”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, background): “…S ∈ R t × n have S m , z m ← 1 / √ tp z m , where p i ≥ u i / 2 r , and The following fact is due to Rudelson [1999], but has since seen many proofs, and follows readily from Noncommutative Bernstein inequalities [Recht 2009], which are very similar to matrix Bernstein inequalities [Zouzias 2011].”
Exact Tensor Completion Using t-SVD (2015, methodology): “In this paper we consider sampling and recovery for 3-rd order tensors using the tensor-SVD (t-SVD) proposed in [1] as a rank-revealing factorization and exploited in [2] for problem of video recovery from missing pixels.”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, background): “We want (16) to hold not just for a single matrix, but uniformly over the set of all unit-norm rank 2 R matrices.”
Analyze gauss: optimal bounds for privacy-preserving principal component analysis (2014, background): “Granularity of Privacy: Two works of Hardt and Roth aim to exploit low coherence of the data matrix, a phenomenon of substantial interest in the (non-private) compressed sensing and matrix completion literature [7, 8, 26, 29, 25], to (privately) obtain good low rank approximations to the data matrix”
Speedup Matrix Completion with Side Information: Application to Multi-Label Learning (2013, methodology): “Following the standard theory for matrix completion [11, 12, 34], we can cast the matrix completion task into the following optimization problem:”
Confusion Matrix Stability Bounds for Multiclass Classification (2012, methodology): “our primary concern — as we shall see, though, getting bounds on the confusion matrix entails, as a byproduct, bounds on the misclassiﬁcation rate. Building on matrix-based concentration inequalities [1,2,3,4,5], also referred to as noncommutative concentration inequalities, we establish a stability”
Algorithmic Regularization in Over-parameterized Matrix Recovery (2017, background): “Early works on matrix sensing and matrix factorization problems use convex relaxation (nuclear norm minimization) approaches and obtain tight sample complexity bounds [24, 29, 7, 23, 6].”
Value function approximation via low-rank models (2015, background): “2The unknown support of the errors makes the problem more difficult than the matrix completion problem that has recently been much studied [10], [11].”
Recovering Low-Rank Matrices From Few Coefficients in Any Basis (2009, methodology): “The author of [25] presents our methods in a language more suitable for an audience from mathematics or information theory.”
Estimation of high-dimensional low-rank matrices (2009, background): “Cand`es and Recht (2009), Cand`es and Tao (2009), Gross (2009), Recht (2009) considered the nonnoisy setting ( ξ i ≡ 0) of the matrix completion problem under conditions that the singular vectors of A ∗ are suﬃciently spread out on the unit sphere or “incoherent.””
A quantum-inspired classical algorithm for recommendation systems (2018, background): “This is impractical and worse than matrix completion, for which we can prove correctness given as little as an Θ̃( k m+n ) fraction of input data [25].”