Candes, Emmanuel and Rudelson, Mark and Tao, Terence and Vershynin, Roman
(2005)
*Error correction via linear programming.*
In:
46th Annual IEEE Symposium on Foundations of Computer Science.
Annual IEEE Symposium on Foundations of Computer Science.
IEEE Computer Society Press
, Los Alamitos, CA, pp. 668-681.
ISBN 0-7695-2468-0
http://resolver.caltech.edu/CaltechAUTHORS:20110609-075242535

PDF
- Published Version
See Usage Policy. |

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110609-075242535

## Abstract

Suppose we wish to transmit a vector f Є R^n reliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y? This paper proves that under suitable conditions on the coding matrix A, the input f is the unique solution to the ℓ_1 -minimization problem (‖x‖ℓ_1: = ∑_i |xi|) min ‖y − Ag‖ℓ_1 g^∈Rn provided that the fraction of corrupted entries is not too large, i.e. does not exceed some strictly positive constant ρ ∗ (numerical values for ρ ^∗ are given). In other words, f can be recovered exactly by solving a simple convex optimization problem; in fact, a linear program. We report on numerical experiments suggesting that ℓ_1-minimization is amazingly effective; f is recovered exactly even in situations where a very significant fraction of the output is corrupted. In the case when the measurement matrix A is Gaussian, the problem is equivalent to that of counting lowdimensional facets of a convex polytope, and in particular of a random section of the unit cube. In this case we can strengthen the results somewhat by using a geometric functional analysis approach.

Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| |||||||||

Additional Information: | © 2005 IEEE. | |||||||||

Subject Keywords: | linear codes; decoding of (random) linear codes; sparse solutions to underdetermined systems; ℓ_1- minimization; linear programming; restricted orthonormality; Gaussian random matrices | |||||||||

Record Number: | CaltechAUTHORS:20110609-075242535 | |||||||||

Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20110609-075242535 | |||||||||

Official Citation: | Candes, E.; Rudelson, M.; Tao, T.; Vershynin, R.; , "Error correction via linear programming," Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on , vol., no., pp.668-681, 25-25 Oct. 2005 doi: 10.1109/SFCS.2005.5464411 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5464411&isnumber=32664 | |||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||

ID Code: | 23952 | |||||||||

Collection: | CaltechAUTHORS | |||||||||

Deposited By: | Ruth Sustaita | |||||||||

Deposited On: | 09 Jun 2011 17:11 | |||||||||

Last Modified: | 29 Mar 2014 03:25 |

Repository Staff Only: item control page