Dense error correction via l1-minimization
Lists
Only you see this
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...