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 (15)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors
• Joint-sparse recovery from multiple measurements
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
• On Verifiable Sufficient Conditions for Sparse Signal Recovery via ${\ell }_1$ Minimization
• 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 (39)

• Robustly Stable Signal Recovery in Compressed Sensing with Structured Matrix Perturbation
• On risk bounds in isotonic and other shape restricted regression problems
• A new perspective on least squares under convex constraint
• A framework to characterize performance of LASSO algorithms
• New Null Space Results and Recovery Thresholds for Matrix Rank Minimization
• Phase Transitions in Frequency Agile Radar Using Compressed Sensing
• Variational Bayesian algorithm for quantized compressed sensing
• Block-length dependent thresholds in block-sparse compressed sensing
• Orthonormal Expansion l1-Minimization Algorithms for Compressed Sensing
• Sparse Recovery from Nonlinear Measurements with Applications in Bad Data Detection for Power Networks
• Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
• The Gaussian min-max theorem in the Presence of Convexity
• Sharp MSE Bounds for Proximal Denoising
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
• Asymptotically Exact Error Analysis for the Generalized ${\ell }_2^2$-LASSO
• Sharp recovery bounds for convex demixing, with applications
• Meshes that trap random subspaces
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• A rigorous geometry-probability equivalence in characterization of ${\ell }_1$-optimization
• Gordon's inequality and condition numbers in conic optimization
• Regularly random duality
• A performance analysis framework for SOCP algorithms in noisy compressed sensing
• A Unified Approach to Uniform Signal Recovery From Non-Linear Observations
• Guarantees of Total Variation Minimization for Signal Recovery
• Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models
• High dimensional regression and matrix estimation without tuning parameters
• Bounds on restricted isometry constants of random matrices
• Asymptotic Behavior of Adversarial Training in Binary Classification
• Compressed sensing of block-sparse positive vectors
• Asymmetric Little model and its ground state energies
• Towards a better compressed sensing
• A problem dependent analysis of SOCP algorithms in noisy compressed sensing
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
• Low noise sensitivity analysis of Lq-minimization in oversampled systems
• How to exploit prior information in low-complexity models
• Precise Phase Transition of Total Variation Minimization
• Linear under-determined systems with sparse solutions: Redirecting a challenge?