CaltechAUTHORS
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. http://resolver.caltech.edu/CaltechAUTHORS:CANieeetit05

 Preview
PDF
See Usage Policy.

375Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:CANieeetit05

Abstract

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 © 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. 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 CaltechAUTHORS:CANieeetit05 http://resolver.caltech.edu/CaltechAUTHORS:CANieeetit05 http://dx.doi.org/10.1109/TIT.2005.858979 No commercial reproduction, distribution, display or performance rights in this work are provided. 1378 CaltechAUTHORS Archive Administrator 04 Mar 2006 26 Dec 2012 08:44

Repository Staff Only: item control page