The limits of error correction with l<inf>p</inf> decoding

Abstract

An unknown vector f in R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> can be recovered from corrupted measurements y = Af + e where A <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> -minimization (0 <; p ≤ 1) which returns a vector x that minimizes the "l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> -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.

Locations

• arXiv (Cornell University) - View - PDF