Conference proceeding
The limits of error correction with lp decoding
2010 IEEE International Symposium on Information Theory, pp.749-753
06/2010
DOI: 10.1109/ISIT.2010.5513613
Abstract
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 l p -minimization (0 <; p ≤ 1) which returns a vector x that minimizes the "l p -norm" of y-Ax. We give sharp thresholds of the fraction of errors that is recoverable. 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), and 1 for p = 1.
Details
- Title: Subtitle
- The limits of error correction with lp decoding
- Creators
- Meng Wang - Cornell UniversityWeiyu Xu - Cornell UniversityAo Tang - Cornell University
- Resource Type
- Conference proceeding
- Publication Details
- 2010 IEEE International Symposium on Information Theory, pp.749-753
- Publisher
- IEEE
- DOI
- 10.1109/ISIT.2010.5513613
- ISSN
- 2157-8095
- eISSN
- 2157-8117
- Language
- English
- Date published
- 06/2010
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197270802771
Metrics
13 Record Views