Various thresholds for ${\ell }_1$-optimization in compressed sensing

Abstract

Recently, \cite{CRT,DonohoPol} theoretically analyzed the success of a polynomial ${\ell }_1$-optimization algorithm in solving an under-determined system of linear equations. In a large dimensional and statistical context \cite{CRT,DonohoPol} proved that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that ${\ell }_1$-optimization succeeds in solving the system. In this paper, we provide an alternative performance analysis of ${\ell }_1$-optimization and obtain the proportionality constants that in certain cases match or improve on the best currently known ones from \cite{DonohoPol,DT}.

References in corpus (7)

• Weighted ${\ell }_1$ Minimization for Sparse Recovery with Prior Information
• Sparse Recovery of Positive Signals with Minimal Expansion
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Breaking through the Thresholds: an Analysis for Iterative Reweighted ${\ell }_1$ Minimization via the Grassmann Angle Framework
• Robust Recovery of Signals From a Structured Union of Subspaces
• Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation
• Simultaneous support recovery in high dimensions: Benefits and perils of block ${\ell }_1/{\ell }_{\infty }$-regularization

Cited by in corpus (1)

• Block-length dependent thresholds in block-sparse compressed sensing