Verifiable conditions of ${\ell }_1$-recovery of sparse signals with sign restrictions

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 the error bounds for imperfect ${\ell }_1$-recovery in terms of the characteristics underlying these conditions. Furthermore, we demonstrate 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$-semigood. We concentrate on the properties of proposed verifiable sufficient conditions of $s$-semigoodness and describe their limits of performance.

References in corpus (1)

• Verifiable conditions of ${\ell }_1$-recovery of sparse signals with sign restrictions

Cited by in corpus (3)

• Accuracy guarantees for L1-recovery
• Verifiable conditions of ${\ell }_1$-recovery of sparse signals with sign restrictions
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals