Dense error correction via l1-minimization

Abstract

We study the problem of recovering a non-negative sparse signal x isin Ropf <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> from highly corrupted linear measurements y = Ax+e isin Ropf <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> , where e is an unknown (and unbounded) error. Motivated by an observation from computer vision, we prove that for highly correlated dictionaries A, any non-negative, sufficiently sparse signal x can be recovered by solving an lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> -minimization problem: min ||x|| <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> + ||e|| <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> subject to y = Ax + e. If the fraction rho of errors is bounded away from one and the support of x grows sublinearly in the dimension m of the observation, for large m, the above lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> -minimization recovers all sparse signals x from almost all sign-and-support patterns of e. This suggests that accurate and efficient recovery of sparse signals is possible even with nearly 100% of the observations corrupted.

Locations

• arXiv (Cornell University) - View - PDF
• Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) - View - PDF
• IEEE International Conference on Acoustics Speech and Signal Processing - View
• IDEALS (University of Illinois Urbana-Champaign) - View - PDF