Highly robust error correction by convex programming

Details Highly robust error correction by convex programming Highly robust error correction by convex programming

2006-12-22

arxiv.org/abs/cs/0612124v1

Computer Science

Information Theory

23 pages, 2 figures

Scientific paper

This paper discusses a stylized communications problem where one wishes to transmit a real-valued signal x in R^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 is a suitable m by n coding matrix (m >= n), 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 occur upon transmission (or equivalently as if one has 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.

Affiliated with

Also associated with

No associations

Rating

Highly robust error correction by convex programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Highly robust error correction by convex programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Highly robust error correction by convex programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-531061