Optimization Online


On Verifiable Sufficient Conditions for Sparse Signal Recovery via L1 Minimization

A.S. Nemirovski (nemirovs***at***isye.gatech.edu)
A.B. Juditsky (juditsky***at***imag.fr)

Abstract: We propose novel necessary and sufficient conditions for a sensing matrix to be ``s-good'' -- to allow for exact L1-recovery of sparse signals with s nonzero entries when no measurement noise is present. Then we express the error bounds for imperfect L1-recovery (nonzero measurement noise, nearly s-sparse signal, near-optimal solution of the optimization problem yielding the L1-recovery) in terms of the characteristics underlying these conditions. Further, we demonstrate (and this is the principal result of the paper) that these characteristics, although difficult to evaluate, lead to verifiable sufficient conditions for exact sparse L1-recovery and to efficiently computable upper bounds on those s for which a given sensing matrix is s-good. We establish also instructive links between our approach and the basic concepts of the Compressed Sensing theory, like Restricted Isometry or Restricted Eigenvalue properties.

Keywords: sparse recovery, compressed sensing

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 09/15/2008
Entry Accepted: 09/15/2008
Entry Last Modified: 04/20/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society