Various thresholds for ℓ₁-optimization in compressed sensing

2009/07/21 by Mihailo Stojnic, Stojnic, Mihailo · 34 citations
Computer Science · Engineering · Mathematics · #Electrical and Bioimpedance Tomography #FOS: Computer and information sciences #Image and Signal Denoising Methods #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.0907.3666

arxiv created 2009/07/21 · openalex publication_date 2009/07/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recently, \citeCRT,DonohoPol theoretically analyzed the success of a polynomial ℓ₁-optimization algorithm in solving an under-determined system of linear equations. In a large dimensional and statistical context \citeCRT,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 ℓ₁-optimization succeeds in solving the system. In this paper, we provide an alternative performance analysis of ℓ₁-optimization and obtain the proportionality constants that in certain cases match or improve on the best currently known ones from \citeDonohoPol,DT.

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Single-pixel imaging via compressive sampling
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Robust Recovery of Signals From a Structured Union of Subspaces

Cited by

• An RDT based confirmation of Lehner's formula for Kronecker-Gaussian matrices
• Inductive Bias and Spectral Properties of Single-Head Attention in High Dimensions
• Precise Phase Transition of Total Variation Minimization
• Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• How to exploit prior information in low-complexity models
• Asymmetric Little model and its ground state energies
• Low noise sensitivity analysis of Lq-minimization in oversampled systems
• High dimensional regression and matrix estimation without tuning parameters
• CLuP practically achieves ∼ 1.77 positive and ∼ 0.33 negative Hopfield model ground state free energy
• Linear under-determined systems with sparse solutions: Redirecting a challenge?
• The Gaussian min-max theorem in the Presence of Convexity
• Asymptotic Behavior of Adversarial Training in Binary Classification
• A rigorous geometry-probability equivalence in characterization of ℓ₁-optimization
• A CLuP algorithm to practically achieve ∼ 0.76 SK--model ground state free energy
• Sharp recovery bounds for convex demixing, with applications
• Sharp MSE Bounds for Proximal Denoising
• Guarantees of Total Variation Minimization for Signal Recovery
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• A large deviation view of stationarized fully lifted blirp interpolation
• Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques
• Phase retrieval with rank d measurements -- descending algorithms phase transitions
• Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view
• Phase transition of descending phase retrieval algorithms
• Optimal Implicit Bias in Linear Regression
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
• Asymptotically Exact Error Analysis for the Generalized ℓ₂²-LASSO
• Towards a better compressed sensing
• Bounds on restricted isometry constants of random matrices
• Compressed sensing of block-sparse positive vectors
• Block-length dependent thresholds in block-sparse compressed sensing
• A framework to characterize performance of LASSO algorithms
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
• Upper-bounding ℓ₁-optimization weak thresholds

Related

• Optimality of ℓ₂/ℓ₁-optimization block-length dependent thresholds
• Block-length dependent thresholds in block-sparse compressed sensing
• Towards a better compressed sensing
• Lifting ℓ₁-optimization strong and sectional thresholds
• Analysis of The Ratio of ℓ₁ and ℓ₂ Norms in Compressed Sensing