Error correction via linear programming
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.
Additional Information
© 2005 IEEE.Attached Files
Published - Candes2005.pdf
Files
Name | Size | Download all |
---|---|---|
md5:fe5838ab7087ac1620d04d9722d6c731
|
245.7 kB | Preview Download |
Additional details
- Eprint ID
- 23952
- Resolver ID
- CaltechAUTHORS:20110609-075242535
- Created
-
2011-06-09Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Series Name
- Annual IEEE Symposium on Foundations of Computer Science