Dense Error Correction Via l1-Minimization

This paper studies the problem of recovering a sparse signal x is an element of R-n from highly corrupted linear measurements y = Ax + e is an element of R-m, where e is an unknown error vector whose nonzero entries may be unbounded. Motivated by an observation from face recognition in computer vision, this paper proves that for highly correlated (and possibly overcomplete) dictionaries A, any sufficiently sparse signal can be recovered by solving an l(1)-minimization problem min parallel to x parallel to(perpendicular to) + parallel to e parallel to(perpendicular to) subject to y = Ax + e. More precisely, if the fraction of the support of the error e is bounded away from one and the support of is a very small fraction of the dimension m, then as m becomes large the above l(1)-minimization succeeds for all signals and almost all sign-and-support patterns of e. This result suggests that accurate recovery of sparse signals is possible and computationally feasible even with nearly 100% of the observations corrupted. The proof relies on a careful characterization of the faces of a convex polytope spanned together by the standard crosspolytope and a set of independent identically distributed (i. i. d.) Gaussian vectors with nonzero mean and small variance, dubbed the cross-and-bouquet (CAB) model. Simulations and experiments corroborate the findings, and suggest extensions to the result.