The phase diagram of compressed sensing with ${\ell }_0$-norm regularization

Abstract

Noiseless compressive sensing is a two-steps setting that allows for undersampling a sparse signal and then reconstructing it without loss of information. The LASSO algorithm, based on $\lone$ regularization, provides an efficient and robust to address this problem, but it fails in the regime of very high compression rate. Here we present two algorithms based on $\lzero$-norm regularization instead that outperform the LASSO in terms of compression rate in the Gaussian design setting for measurement matrix. These algorithms are based on the Approximate Survey Propagation, an algorithmic family within the Approximate Message Passing class. In the large system limit, they can be rigorously tracked through State Evolution equations and it is possible to exactly predict the range compression rates for which perfect signal reconstruction is possible. We also provide a statistical physics analysis of the $\lzero$-norm noiseless compressive sensing model. We show the existence of both a replica symmetric state and a 1-step replica symmmetry broken (1RSB) state for sufficiently low $\lzero$-norm regularization. The recovery limits of our algorithms are linked to the behavior of the 1RSB solution.

arXiv admin note: substantial text overlap with arXiv:2304.12127

References in corpus (12)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Statistical physics-based reconstruction in compressed sensing
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The spherical 2+p spin glass model: an analytically solvable model with a glass-to-glass transition
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Approximate Survey Propagation for Statistical Inference
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Statistical mechanics approach to 1-bit compressed sensing