Dense Error Correction via l1-Minimization

Wright, John; Ma, Yi

Permalink

https://hdl.handle.net/2142/99607 Copy

Description

Title

Dense Error Correction via l1-Minimization

Author(s)

• Wright, John
• Ma, Yi

Issue Date

2008-07

Keyword(s)

• Sparse signal recovery
• Dense error correction
• l1-minimization
• 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.

Publisher

Coordinated Science Laboratory, University of Illinois at Urbana-Champaign

Series/Report Name or Number

Coordinated Science Laboratory Report no. UILU-ENG-08-2210, DC-237

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/99607

Sponsor(s)/Grant Number(s)

• NSF / CRS-EHS-0509151, CCF-TF-0514955, and NSF IIS 07-03756
• ONR / YIP N00014-05-1-0633
• Microsoft Live Labs Fellowship

Owning Collections