A Caltech Library Service

Decoding by linear programming

Candès, Emmanuel J. and Tao, Terence (2005) Decoding by linear programming. IEEE Transactions on Information Theory, 51 (12). pp. 4203-4215. ISSN 0018-9448. doi:10.1109/TIT.2005.858979.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Candès, Emmanuel J.0000-0001-9234-924X
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. Manuscript received February 2005; revised September 2, 2005. Posted online: 2005-11-21. The work of E. J. Candes is supported in part by the National Science Foundation under Grants DMS 01-40698 (FRG) and ACI-0204932 (ITR), and by an A. P. Sloan Fellowship. The work of T. Tao is supported in part by a grant from the Packard Foundation. The authors wish to thank Rafail Ostrovsky for pointing out possible connections between their earlier work and the decoding problem. E. J. Candes would also like to acknowledge inspiring conversations with Leonard Schulmann and Justin Romberg.
Subject Keywords:Basis pursuit, Gaussian random matrices, decoding of (random) linear codes, duality in optimization, linear codes, linear programming, principal angles, restricted orthonormality, singular values of random matrices, sparse solutions to underdetermined systems
Issue or Number:12
Record Number:CaltechAUTHORS:CANieeetit05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1378
Deposited By: Archive Administrator
Deposited On:04 Mar 2006
Last Modified:08 Nov 2021 19:09

Repository Staff Only: item control page