Message passing algorithms for compressed sensing: I. motivation and construction

By David L. Donoho, Arian Maleki, Andrea Montanari. 2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo), 2009

571 citations recorded by the source corpus.

In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements. The new algorithms are broadly referred to as AMP, for approximate message passing. This is the first of two conference papers describing the derivation of these algorithms, connection with the related literature, extensions of the original framework, and new empirical evidence. In particular, the present paper outlines the derivation of AMP from standard sum-product belief propagation, and its extension in several directions. We also discuss relations with formal calculations based on statistical mechanics methods.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/54476dcb31c2514404652bac1ac9fe6bda72ccc2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Sparse Signal Processing for Grant-Free Massive Connectivity: A Future Paradigm for Random Access Protocols in the Internet of Things (2018, methodology): “4) Bayesian Framework for Denoiser Design: On the other hand, if the distribution of x is known in (2), we can design the minimum mean-squared error (MMSE) denoiser via the Bayesian approach to minimize the MSE for the estimation of x as given in (4) [18].”
Compressive phase retrieval via generalized approximate message passing (2012, methodology): “The approximate message passing (AMP) algorithm was recently proposed by Donoho, Maleki, and Montanari [24], [25] for the task estimating a signal vector x ∈ R from linearly compressed and additive-Gaussian-noise corrupted measurements(2)”
Non-convex Optimization for Machine Learning (2017, methodology): “A flurry of work then followed on relaxation-based techniques [Candès, 2008, Donoho et al., 2009, Foucart, 2010, Negahban et al., 2012] that vastly expanded the scope of the problems being studied, the techniques being applied, as well as their analyses.”
Sparse Activity Detection for Massive Connectivity (2018, methodology): “Similarly, a Bayesian approach is used to design the AMP algorithm in [16], [17] by accounting for the input distribution.”
The Noise-Sensitivity Phase Transition in Compressed Sensing (2010, background): “As discussed in [16], AMP solves these problems.”
Compressive Sensing-Based Adaptive Active User Detection and Channel Estimation: Massive Access Meets Massive MIMO (2019, methodology): “However, a key observation is that, in the large system limit with K → ∞, the messages ξ̂ g→k(xk) can be approximated by Gaussian distributions [33].”
Orthogonal AMP (2016, unknown): “When A is IID Gaussian, it is shown in [7] that the fixed-point equation of the SE for AMP coincides with that of the MMSE performance for a large system.”
Vector Approximate Message Passing (2019, methodology): “We refer the reader to [3], [24] for details on the message-passing derivation of AMP, noting connections to the general framework of expectation propagation (EP) [13], [14].”
Learning Optimal Nonlinearities for Iterative Thresholding Algorithms (2015, background): “[13], as well as its Bayesian extensions [14, 15].”
AMP-Inspired Deep Networks for Sparse Linear Inverse Problems (2016, unknown): “5AMP with MSE-optimal denoising was first described in [23].”
Statistical physics-based reconstruction in compressed sensing (2011, methodology): “In particular, adaptations of belief propagation have been developed for the compressed sensing reconstruction, both in the context of (cid:96) 1 reconstruction [11, 22, 23], and in a probabilistic approach [24].”