Files in this item



application/pdfUILU-ENG-08-2210_DC-237 assembled.pdf (819kB)
(no description provided)PDF


Title:Dense Error Correction via l1-Minimization
Author(s):Wright, John; Ma, Yi
Subject(s):Sparse signal recovery
Dense error correction
Gaussian random ensemble
Polytope neighborliness
Abstract:In this paper, we study the problem of recovering a sparse signal x 2 Rn from highly corrupted linear measurements y = Ax+e 2 Rm, where e is an unknown error vector whose nonzero entries could be unbounded. Motivated by the problem of face recognition in computer vision, we will prove that if a signal has a sufficiently sparse representation with respect to a highly correlated dictionary A (either overcomplete or not), then with overwhelming probability, it can be recovered by solving the following l1-minimization problem: min kxk1 + kek1 subject to y = Ax + e; even for very dense e. More precisely, in this paper we prove that under the above conditions, for any _ < 1, as m goes to infinity, solving the above l1-minimization problem correctly recovers any sparse enough non-negative signal x from almost any error e with support size _ _m. This result suggests that accurate recovery of sparse signals is possible and computationally feasible even with errors asymptotically approaching 100%! The proof relies on a careful characterization of the neighborliness of a convex polytope spanned together by the standard cross polytope and a nonzero mean Gaussian ensemble with a small variance, which we call the “cross-and-bouquet” model. The high neighborliness of this polytope enables the striking error correction ability of the above l1-minimization. We will also show simulations and experimental results that corroborate our findings.
Issue Date:2008-07
Publisher:Coordinated Science Laboratory, University of Illinois at Urbana-Champaign
Series/Report:Coordinated Science Laboratory Report no. UILU-ENG-08-2210, DC-237
Genre:Technical Report
Sponsor:NSF / CRS-EHS-0509151, CCF-TF-0514955, and NSF IIS 07-03756
ONR / YIP N00014-05-1-0633
Microsoft Live Labs Fellowship
Date Available in IDEALS:2018-04-04

This item appears in the following Collection(s)

Item Statistics