sparse recovery

Verifiable conditions of $\ell_1hBcrecovery for sparse signals with sign restrictions

  • Anatoli Juditsky
  • Fatma Kılınç-Karzan
  • Arkadi Nemirovski
    • Categories Statistics Tags ,

    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 … Read more

    On Verifiable Sufficient Conditions for Sparse Signal Recovery via L1 Minimization

  • Anatoli Juditsky
  • Arkadi Nemirovski
    • Categories Convex Optimization, Statistics Tags ,

    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 … Read more