Statistical mechanics approach to 1-bit compressed sensing
Statistical mechanics approach to 1-bit compressed sensing
复制标题
1 位压缩感知的统计力学方法
DOI：
10.1088/1742-5468/2013/02/p02041
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Yingying Xu and Yoshiyuki Kabashima
中科院分区：
文献类型：
--
作者：
Haiping Huang;Yoshiyuki Kabashima;Yingying Xu and Yoshiyuki Kabashima
压缩感知是一个框架，可以从较低维度 M< N 的线性变换 y∈ R M 中恢复 N 维稀疏向量 x∈ R N 。最近提出了一种通过仅使用 y 每个条目的符号来恢复 x 来进一步减小压缩表达式的数据大小的方案。这通常称为 1 位压缩感知。在这里，我们使用统计力学方法分析了基于 l 1-范数的 1 位压缩感知信号恢复方案的典型性能。我们表明，在副本对称 ansatz 下，副本方法预测的信号恢复性能与早期开发的近似恢复算法的实验结果具有良好的一致性，对于破坏副本对称性的模式来说，副本方法是局部不稳定的。这表明基于 l 1 的恢复问题通常具有许多相似恢复精度的局部最优，这可以通过近似算法来实现。我们还开发了另一种受空腔方法启发的近似恢复算法。数值实验表明，当原始信号中非零项的密度较大时，新算法比上述方案提供了更好的性能，并且计算成本较低。
Compressed sensing is a framework that makes it possible to recover an N-dimensional sparse vector x∈ R N from its linear transformation y∈ R M of lower dimensionality M< N. A scheme further reducing the data size of the compressed expression by using only the sign of each entry of y to recover x was recently proposed. This is often termed 1-bit compressed sensing. Here, we analyze the typical performance of an l 1-norm-based signal recovery scheme for 1-bit compressed sensing using statistical mechanics methods. We show that the signal recovery performance predicted by the replica method under the replica symmetric ansatz, which turns out to be locally unstable for modes breaking the replica symmetry, is in good consistency with experimental results of an approximate recovery algorithm developed earlier. This suggests that the l 1-based recovery problem typically has many local optima of a similar recovery accuracy, which can be achieved by the approximate algorithm. We also develop another approximate recovery algorithm inspired by the cavity method. Numerical experiments show that when the density of nonzero entries in the original signal is relatively large the new algorithm offers better performance than the abovementioned scheme and does so with a lower computational cost.