Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2008 | Published
Journal Article Open

Highly Robust Error Correction by Convex Programming

Abstract

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.

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 http://ieeexplore.ieee.org.

Attached Files

Published - CANieeetit08.pdf

Files

CANieeetit08.pdf
Files (501.5 kB)
Name Size Download all
md5:d3c4bb580f767c2c5ecda7b942e54b6f
501.5 kB Preview Download

Additional details

Created:
September 14, 2023
Modified:
October 23, 2023