The limits of error correction with lp decoding
An unknown vector f in R<sup>n</sup> can be recovered from corrupted measurements y = Af + e where A<sup>m×n</sup>(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<inf>p</inf>-minimization (0 < p ≤ 1) which returns a vector x that minimizes the “l<inf>p</inf>-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 ⅔ for all p in (0, 1), and 1 for p = 1.