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

  1. Yuanzhi Li
  2. Francis R. Bach
  3. Michael I. Jordan
  4. Jason D. Lee
  5. Yoshua Bengio
  6. Tengyu Ma
  7. Zeyuan Allen-Zhu
  8. Ruslan Salakhutdinov

In Computational Mathematics

  1. B. Recht
  2. Michael I. Jordan
  3. E.J. Candes
  4. Shuchin Aeron
  5. Prateek Jain
  6. Alex Gittens
  7. Justin K. Romberg
  8. Joel A. Tropp

In Computational Mechanics

  1. E.J. Candes
  2. Martin J. Wainwright
  3. Prateek Jain
  4. Justin K. Romberg
  5. Wotao Yin
  6. Yudong Chen
  7. B. Recht
  8. Sujay Sanghavi

In Representation & Self-Supervised Learning

  1. Yuanzhi Li
  2. Prateek Jain
  3. E.J. Candes
  4. Yuxin Chen
  5. Joel A. Tropp
  6. Martin J. Wainwright
  7. John Wright
  8. Justin K. Romberg

In Mathematical Optimization

  1. Prateek Jain
  2. Srinadh Bhojanapalli
  3. E.J. Candes
  4. Justin K. Romberg
  5. Sujay Sanghavi
  6. Zhi-Quan Tom Luo
  7. Ruoyu Sun
  8. Michael I. Jordan

Citations in the corpus