The Limits of Error Correction with lp Decoding

Details The Limits of Error Correction with lp Decoding The Limits of Error Correction with lp Decoding

2010-06-02

arxiv.org/abs/1006.0277v1

Computer Science

Information Theory

5 pages, 1 figure. ISIT 2010

Scientific paper

An unknown vector f in R^n can be recovered from corrupted measurements y = Af + e where A^(m*n)(m>n) is the coding matrix if the unknown error vector e is sparse. We investigate the relationship of the fraction of errors and the recovering ability of lp-minimization (0 < p <= 1) which returns a vector x minimizing the "lp-norm" of y - Ax. We give sharp thresholds of the fraction of errors that determine the successful recovery of f. If e is an arbitrary unknown vector, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. If e has fixed support and fixed signs on the support, the threshold is 2/3 for all p in (0, 1), while the threshold is 1 for l1-minimization.

Affiliated with

Also associated with

No associations

Rating

The Limits of Error Correction with lp Decoding 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 The Limits of Error Correction with lp Decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Limits of Error Correction with lp Decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-512283