Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery

Abstract

Noiseless compressive sensing is a protocol that enables undersampling and later recovery of a signal without loss of information. This compression is possible because the signal is usually sufficiently sparse in a given basis. Currently, the algorithm offering the best tradeoff between compression rate, robustness, and speed for compressive sensing is the LASSO (l1-norm bias) algorithm. However, many studies have pointed out the possibility that the implementation of lp-norms biases, with p smaller than one, could give better performance while sacrificing convexity. In this work, we focus specifically on the extreme case of the l0-based reconstruction, a task that is complicated by the discontinuity of the loss. In the first part of the paper, we describe via statistical physics methods, and in particular the replica method, how the solutions to this optimization problem are arranged in a clustered structure. We observe two distinct regimes: one at low compression rate where the signal can be recovered exactly, and one at high compression rate where the signal cannot be recovered accurately. In the second part, we present two message-passing algorithms based on our first results for the l0-norm optimization problem. The proposed algorithms are able to recover the signal at compression rates higher than the ones achieved by LASSO while being computationally efficient.

References in corpus (17)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• The structural glass transition and the entropy of the metastable states
• Phase Transitions in the Coloring of Random Graphs
• Asymptotic Analysis of MAP Estimation via the Replica Method and 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
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Approximate Survey Propagation for Statistical Inference
• The estimation error of general first order methods
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Statistical mechanics approach to 1-bit compressed sensing