A Caltech Library Service

Highly Robust Error Correction by Convex Programming

Candès, Emmanuel J. and Randall, Paige A. (2008) Highly Robust Error Correction by Convex Programming. IEEE Transactions on Information Theory, 54 (7). pp. 2829-2840. ISSN 0018-9448. doi:10.1109/TIT.2008.924688.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper discusses a stylized communications problem where one wishes to transmit a real-valued signal x ∈ ℝ^n (a block of n pieces of information) to a remote receiver. We ask whether it is possible to transmit this information reliably when a fraction of the transmitted codeword is corrupted by arbitrary gross errors, and when in addition, all the entries of the codeword are contaminated by smaller errors (e.g., quantization errors). We show that if one encodes the information as Ax where A ∈ ℝ^(m x n) (m ≥ n) is a suitable coding matrix, there are two decoding schemes that allow the recovery of the block of n pieces of information x with nearly the same accuracy as if no gross errors occurred upon transmission (or equivalently as if one had an oracle supplying perfect information about the sites and amplitudes of the gross errors). Moreover, both decoding strategies are very concrete and only involve solving simple convex optimization programs, either a linear program or a second-order cone program. We complement our study with numerical simulations showing that the encoder/decoder pair performs remarkably well.

Item Type:Article
Related URLs:
URLURL TypeDescription
Candès, Emmanuel J.0000-0001-9234-924X
Additional Information:© Copyright 2008 IEEE. Reprinted with permission. Manuscript received December 17, 2006; revised December 4, 2007. [Date Published in Issue: 2008-06-17] This work was supported in part by the National Science Foundation (NSF) under Grants ITR ACI-0204932 and CCF515362 and by the 2006 Waterman Award (NSF). The material in this paper was presented at WavE 2006, Lausanne, Switzerland, July 2006. E.J. Candès would like to thank the Centre Interfacultaire Bernoulli of the Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, for hospitality during June and July 2006. The authors would like to thank Mike Wakin for his careful reading of the manuscript and the anonymous referees and the Associate Editor for their useful comments. Communicated by A.J. Goldsmith, Associate Editor for Communications. Color versions of Figures 1 and 2 in this paper are available online at
Funding AgencyGrant Number
National Science FoundationITR ACI-0204932
National Science FoundationCCF515362
National Science Foundation2006 Waterman Award
Subject Keywords:Decoding of (random) linear codes, Gaussian random matrices and random projections, linear codes, ℓ1 minimization, linear programming, restricted orthonormality, second-order cone programming, sparse solutions to underdetermined systems, the Dantzig selector
Issue or Number:7
Record Number:CaltechAUTHORS:CANieeetit08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11149
Deposited By: Archive Administrator
Deposited On:18 Jul 2008 21:31
Last Modified:08 Nov 2021 21:33

Repository Staff Only: item control page