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

Anatoli Juditsky (juditskyimag.fr)
Fatma Kilinc Karzan (fkilincgatech.edu)
Arkadi Nemirovski (nemirovsisye.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 )

Citation:

Download: [PDF]

Entry Submitted: 03/31/2009
Entry Accepted: 03/31/2009
Entry Last Modified: 09/22/2010

Modify/Update this entry