Phase diagram of compressed sensing with l0-norm regularization

Noiseless compressive sensing is a two-step setting that allows for undersampling a sparse signal and then reconstructing it without loss of information. The LASSO algorithm, based on ℓ1 regularization, provides an efficient and robust way to address this problem, but it fails in the regime of very high compression rate. Here we present two algorithms, based on ℓ0 -norm regularization, that outperform 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 ℓ0 -norm noiseless compressive sensing model. We show the existence of both a replica symmetric state and a one-step replica symmmetry broken (1RSB) state for sufficiently low ℓ0 -norm regularization. The recovery limits of our algorithms are linked to the behavior of the 1RSB solution.