Compressed Sensing and Robust Recovery of Low Rank Matrices

Authors

M. Fazel, E. Candes, B. Recht, P. Parrilo

Year

2008

Conference Paper

Source

42nd Asilomar Conference on Signals, Systems and Computers

Identifiers

DOI 10.1109/ACSSC.2008.5074571

Abstract¶

In this paper, we focus on compressed sensing and recovery schemes for low-rank matrices, asking under what conditions a low-rank matrix can be sensed and recovered from incomplete, inaccurate, and noisy observations. We consider three schemes, one based on a certain Restricted Isometry Property and two based on directly sensing the row and column space of the matrix. We study their properties in terms of exact recovery in the ideal case, and robustness issues for approximately low-rank matrices and for noisy measurements.

Summary¶

Extends compressed-sensing recovery ideas from sparse vectors to low-rank matrices through nuclear-norm minimization. The paper helped establish low-rank matrix recovery as a convex-optimization problem with stability guarantees under incomplete or noisy measurements.