Optimization Online


Verifiable conditions of $\ell_1$-recovery for sparse signals with sign restrictions

Anatoli Juditsky (juditsky***at***imag.fr)
Fatma Kilinc Karzan (fkilinc***at***gatech.edu)
Arkadi Nemirovski (nemirovs***at***isye.gatech.edu)

Abstract: We propose necessary and sufficient conditions for a sensing matrix to be ``$s$-semigood'' -- to allow for exact $\ell_1$-recovery of sparse signals with at most $s$ nonzero entries under sign restrictions on part of the entries. We express error bounds for imperfect $\ell_1$-recovery in terms of the characteristics underlying these conditions. These characteristics, although difficult to evaluate, lead to verifiable sufficient conditions for exact sparse $\ell_1$-recovery and thus efficiently computable upper bounds on those $s$ for which a given sensing matrix is $s$-semigood. We examine the properties of proposed verifiable sufficient conditions, describe their limits of performance and provide numerical examples comparing them with other verifiable conditions from the literature.

Keywords: compressive sensing, sparse recovery

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


Download: [PDF]

Entry Submitted: 03/31/2009
Entry Accepted: 03/31/2009
Entry Last Modified: 09/22/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