Decoding by linear programming

By E.J. Candes, Terence Tao. 2005

7,654 citations recorded by the source corpus.

This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.

Subfields: Computational Mechanics, Computer Networks and Communications, Control and Systems Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

  1. E.J. Candes
  2. Martin J. Wainwright
  3. Francis R. Bach
  4. Julien Mairal
  5. Yonina C. Eldar
  6. Richard Baraniuk
  7. Prateek Jain
  8. Wotao Yin

In Computer Networks and Communications

  1. Ali H. Sayed
  2. Martin J. Wainwright
  3. Angelia Nedić
  4. Francis R. Bach
  5. Tong Zhang
  6. Michael G. Rabbat
  7. Richard Baraniuk
  8. Wotao Yin

In Control and Systems Engineering

  1. Francis R. Bach
  2. Cun-Hui Zhang
  3. Martin J. Wainwright
  4. Nati Srebro
  5. Peter Buhlmann
  6. David L. Donoho
  7. Steven L. Brunton
  8. E.J. Candes

Citations in the corpus