Message-passing algorithms for compressed sensing
Message-passing algorithms for compressed sensing
复制标题
DOI：
10.1073/pnas.0909892106
复制
发表时间：
2009-11-10
影响因子：
11.1
通讯作者：
Montanari, Andrea
中科院分区：
文献类型：
--
作者：
Donoho, David L.;Maleki, Arian;Montanari, Andrea
压缩传感旨在调解某些高维信号，但通过利用信号特性来准确地重建它们。当要回收的对象在已知的基础上足够稀疏时，可以进行准确的重建。当前，当通过凸优化重建时，最著名的稀疏量采样折衷是实现，这在重要的大规模应用中很昂贵。快速迭代阈值算法已被深入研究，作为大规模问题凸优化的替代方法。不幸的是，已知的快速算法比凸优化的稀疏性量采样更差。我们为迭代阈值引入了一种简单的无成本修改，从而使新算法的稀疏量采样折衷与相应的凸优化过程相当。新的迭代阈值算法的灵感来自图形模型中的信念传播。我们对新算法的稀疏量采样折衷的经验测量与理论计算相符。我们表明，州进化形式主义正确地得出了真正的稀疏性采样折衷。基于随机凸多图形的早期计算与这种理论形式主义显然是截然不同的一致性。
Compressed sensing aims to undersample certain high-dimensional signals yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity-undersampling tradeoff is achieved when reconstructing by convex optimization, which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity-undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity-undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity-undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity-undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this apparently very different theoretical formalism.