The limits of error correction with lp decoding

An unknown vector f in Rⁿ 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.