Generalized approximate message passing for estimation with random linear mixing

By Sundeep Rangan. IEEE International Symposium on Information Theory. Proceedings, 2010

1,159 citations recorded by the source corpus.

We consider the estimation of a random vector observed through a linear transform followed by a componentwise probabilistic measurement channel. Although such linear mixing estimation problems are generally highly non-convex, Gaussian approximations of belief propagation (BP) have proven to be computationally attractive and highly effective in a range of applications. Recently, Bayati and Montanari have provided a rigorous and extremely general analysis of a large class of approximate message passing (AMP) algorithms that includes many Gaussian approximate BP methods. This paper extends their analysis to a larger class of algorithms to include what we call generalized AMP (G-AMP). G-AMP incorporates general (possibly non-AWGN) measurement channels. Similar to the AWGN output channel case, we show that the asymptotic behavior of the G-AMP algorithm under large i.i.d. Gaussian transform matrices is described by a simple set of state evolution (SE) equations. The general SE equations recover and extend several earlier results, including SE equations for approximate BP on general output channels by Guo and Wang.

Subfields: Computational Mechanics, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/280e863e57e10c8501c67c5cad7f159d6c730571

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 Networks and Communications

In Signal Processing

Citations in the corpus

Optimal errors and phase transitions in high-dimensional generalized linear models (2017, methodology): “While standard compressed sensing focused on the linear case –where φ(z,A) = z+A with a Gaussian noise A– the generalized case was also widely studied [12, 13], especially for quantized output [14] and 1-bit compressed sensing [6,15] where φ(z,A) = sign(z +A), as well as for compressive phase retrie”
Compressive phase retrieval via generalized approximate message passing (2012, methodology): “The Generalized-AMP (GAMP) algorithm proposed by Rangan [23] then extends the methodology of AMP to the generalized linear measurement model”
Statistical Mechanics of Optimal Convex Inference in High Dimensions (2016, methodology): “We compare the normalized MSE, or fraction of unexplained variance q̄s predicted by our theory of optimal regularized M-estimation (solid line), with simulations (error bars) of Bayes-optimal approximate message passing [37].”
A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $\ell ^{0}$ Norm (2008, background): “In addition to EM-BP, the belief propagation approach to the sparse recovery problem has been widely investigated in [2],[3],[4],[5],[6],[7].”
An equivalence between high dimensional Bayes optimal inference and M-estimation (2016, background): “These equations were described in [9], and special cases of them were studied in various works (see e.”
Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results (2013, background): “Donoho and Montanari also make interesting connections with rigorous work in statistical physics, namely to the so-called Shcherbina-Tirozzi model (Shcherbina and Tirozzi (2003) and Talagrand (2003)) and other heuristic approaches based on approximate message passing (Rangan (2011)).”
Massive Connectivity With Massive MIMO—Part I: Device Activity Detection and Channel Estimation (2017, background): “Then, the state evolution is the following recursion for t ≥ 0 [18], [19], [26], [28]:”
Channel Estimation in Broadband Millimeter Wave MIMO Systems With Few-Bit ADCs (2016, methodology): “Remarkably, when A is very large with IID (sub)Gaussian entries, the behavior of GAMP is rigorously characterized by a scalar state evolution [24], [41].”
Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices (2012, background): “Note also that due to the self-averaging property we do not distinguish in what follows between the mean-squared error (9) and the squared error E = ∑N i=1(〈xi〉 − si)2/N .”
Vector Approximate Message Passing (2019, background): “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].”
From Denoising to Compressed Sensing (2014, background): “The approximate message passing algorithm has been studied carefully and extended in many different directions by many researchers in the last ﬁve years [10], [19], [21], [28], [36]–[38], [40]–[48].”
Matrix-Calibration-Based Cascaded Channel Estimation for Reconfigurable Intelligent Surface Assisted Multiuser MIMO (2019, methodology): “To tackle this challenge, we introduce additional approximations to the messages based on the approximate message passing (AMP) framework [15], [16].”
AMP-Inspired Deep Networks for Sparse Linear Inverse Problems (2016, background): “For this, it may be possible to unfold the generalized AMP [50] and VAMP [51] algorithms into networks and learn improved network parameters from training data.”
Learning Optimal Nonlinearities for Iterative Thresholding Algorithms (2015, methodology): “We also consider the MMSE variant of the generalized AMP (GAMP) algorithm [19], which is known to be nearly optimal for recovery of sparse signals from random measurements.”