Recovering Low-Rank Matrices From Few Coefficients in Any Basis
By David Gross. 2009
962 citations recorded by the source corpus.
We present novel techniques for analyzing the problem of low-rank matrix recovery. The methods are both considerably simpler and more general than previous approaches. It is shown that an unknown matrix of rank can be efficiently reconstructed from only randomly sampled expansion coefficients with respect to any given matrix basis. The number quantifies the “degree of incoherence” between the unknown matrix and the basis. Existing work concentrated mostly on the problem of “matrix completion” where one aims to recover a low-rank matrix from randomly selected matrix elements. Our result covers this situation as a special case. The proof consists of a series of relatively elementary steps, which stands in contrast to the highly involved methods previously employed to obtain comparable results. In cases where bounds had been known before, our estimates are slightly tighter. We discuss operator bases which are incoherent to all low-rank matrices simultaneously. For these bases, we show that randomly sampled expansion coefficients suffice to recover any low-rank matrix with high probability. The latter bound is tight up to multiplicative constants.
Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics, Representation & Self-Supervised Learning, Mathematical Optimization
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
- Yuanzhi Li
- Francis R. Bach
- Michael I. Jordan
- Jason D. Lee
- Yoshua Bengio
- Tengyu Ma
- Zeyuan Allen-Zhu
- Ruslan Salakhutdinov
In Computational Mathematics
- B. Recht
- Michael I. Jordan
- E.J. Candes
- Shuchin Aeron
- Prateek Jain
- Alex Gittens
- Justin K. Romberg
- Joel A. Tropp
In Computational Mechanics
- E.J. Candes
- Martin J. Wainwright
- Prateek Jain
- Justin K. Romberg
- Wotao Yin
- Yudong Chen
- B. Recht
- Sujay Sanghavi
In Representation & Self-Supervised Learning
- Yuanzhi Li
- Prateek Jain
- E.J. Candes
- Yuxin Chen
- Joel A. Tropp
- Martin J. Wainwright
- John Wright
- Justin K. Romberg
In Mathematical Optimization
- Prateek Jain
- Srinadh Bhojanapalli
- E.J. Candes
- Justin K. Romberg
- Sujay Sanghavi
- Zhi-Quan Tom Luo
- Ruoyu Sun
- Michael I. Jordan
Citations in the corpus
- Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “The sample size is improved toO(nk log(n)) in subsequent papers [Candès and Tao, 2010, Recht, 2011, Gross, 2011].”
- 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”
- Guaranteed Matrix Completion via Non-Convex Factorization (2014, methodology): “The resampling scheme (a.k.a. golfing scheme [6]) can be used at almost no cost for the nuclear norm approach [6], [7], [33], but for the alternating minimization it causes many issues.”
- Estimation of high-dimensional low-rank matrices (2009, background): “, for example, Bunea, Tsybakov and Wegkamp (2007), Koltchinskii (2008), Bickel, Ritov and Tsybakov (2009), Dalalyan and Tsybakov (2008).”
- 1-Bit Matrix Completion (2012, background): “While many of these applications have a relatively long history, recent advances in the closely related field of compressed sensing [13,21,23] have enabled a burst of progress in the last few years, and we now have a strong base of theoretical results concerning matrix completion [15–17,25,30,36,37,”
- Exact Tensor Completion Using t-SVD (2015, methodology): “We will use an approach called Golfing Scheme introduced by Gross [36] and we will follow the idea in [11][28] where the strategy is to construct Y iteratively.”
- Nuclear norm penalization and optimal rates for noisy low rank matrix completion (2010, background): “Then the problem of estimation of A0 coincides with the problem of matrix completion under uniform sampling at random (USR) as studied in the non-noisy case (ξi = 0) in [14, 21], and in the noisy case in [13, 23].”
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow (2015, background): “Subsequently, a series of papers (Candès & Recht, 2009; Gross, 2011; Recht, 2011; Candès et al., 2014) showed that trace minimization and related convex optimization approaches also work for other measurement ensembles such as those arising in matrix completion and related problems.”
- PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming (2011, background): “This is in stark contrast with David Gross’ approach [13] which requires a very small misfit, i.e. an error of at most 1/n2.”
- Low-rank matrix recovery from errors and erasures (2011, methodology): “The version presented below is first proved in [12], [9] Then for all t ≥ 0 we have W.L.O.G. we only consider the case n 1 = n 2 = n .”
- Tighter Low-rank Approximation via Sampling the Leveraged Element (2014, background): “[14] D.”