The phase diagram of compressed sensing with ℓ_0-norm regularization
Damien Barbier, Carlo Lucibello, Luca Saglietti, Florent Krzakala, Lenka Zdeborová
无噪音压缩传感是一个两步设置,允许对稀疏信号进行采样,然后在不丢失信息的情况下重建它。 LASSO算法基于正则化,为解决这个问题提供了一种高效和稳健的算法,但它在压缩率非常高的制程中失败。 在这里,我们介绍了基于-规范正则化的两种算法,这些算法在测量矩阵的 Gaussian 设计设置中的压缩率方面优于 LASSO。 这些算法基于近似调查传播,这是近似消息传递类中的算法家族。 在大型系统限制中,它们可以通过状态进化方程进行严格的跟踪,并且可以精确预测可能完美信号重建的范围压缩速率。 我们还提供了 -orm 无噪声抗压传感模型的统计物理分析。 我们展示了复制对称状态和1步复制对称断裂(1RSB)状态的存在,以实现足够低的规范正则化。 我们算法的恢复限制与 1RSB 解决方案的行为相关联。
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 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 -norm regularization instead that outperform the LASSO in terms of compression rate in the Gaussian design setting for measurement matrix. Thes...
