2024/07/31 by Damien Barbier, Barbier, Damien, Carlo Lucibello +7 · 1 citation
Mathematics · Medicine · Physics and Astronomy · #Advanced X-ray Imaging Techniques #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Medical Imaging Techniques and Applications #Numerical methods in inverse problems
paper · pdf · doi:10.48550/arxiv.2408.08319
openalex publication_date 2024/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
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.