Dense error correction via l1-minimization

John Wright, Yi Ma

Abstract

We study the problem of recovering a non-negative sparse signal x isin Ropfn from highly corrupted linear measurements y = Ax+e isin Ropfm, 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 lscr1-minimization problem: min ||x||1 + ||e||1 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 lscr1-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.
BibTeX
@article{wright2010dense,
  author = {John Wright and Yi Ma},
  title = {{Dense error correction via l1-minimization}},
  journal = {IEEE Trans. Information Theory},
  year = {2010},
  doi = {10.1109/tit.2010.2048473},
}

Loading related content...

Figure