On Verifiable Sufficient Conditions for Sparse Signal Recovery via $\ell_1$ Minimization

Details On Verifiable Sufficient Conditions for Sparse Signal Recovery via $\ell_1$ Minimization On Verifiable Sufficient Conditions for Sparse Signal Recovery via $\ell_1$ Minimization

2008-09-16

arxiv.org/abs/0809.2650v2

Mathematics

Optimization and Control

Scientific paper

We propose novel necessary and sufficient conditions for a sensing matrix to be "$s$-good" - to allow for exact $\ell_1$-recovery of sparse signals with $s$ nonzero entries when no measurement noise is present. Then we express the error bounds for imperfect $\ell_1$-recovery (nonzero measurement noise, nearly $s$-sparse signal, near-optimal solution of the optimization problem yielding the $\ell_1$-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 $\ell_1$-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.

Affiliated with

Also associated with

No associations

Rating

On Verifiable Sufficient Conditions for Sparse Signal Recovery via $\ell_1$ Minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Verifiable Sufficient Conditions for Sparse Signal Recovery via $\ell_1$ Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Verifiable Sufficient Conditions for Sparse Signal Recovery via $\ell_1$ Minimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-570439