Dense error correction via L1-minimization

Abstract

We study the problem of recovering a non-negative sparse signal x ∈ ℝn from highly corrupted linear measurements y = Ax+e ∈ ℝm, 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 ℓ1-minimization problem: min ∥x∥ 1 + ∥e∥1 subject to y = Ax + e. If the fraction ρ 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 ℓ1-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. ©2009 IEEE.