pith. sign in

arxiv: 1907.02247 · v3 · pith:AUFV7KTZnew · submitted 2019-07-04 · 💻 cs.IT · math.IT

A New Insight into GAMP and AMP

Lei Liu , Ying Li , Chongwen Huang , Chau Yuen , Yong Liang Guan This is my paper

Pith reviewed 2026-05-25 09:26 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords expectation propagationmessage passingGAMPAMPapproximate message passingunificationnon-linear processing
0
0 comments X

The pith

Neglecting high-order infinitesimal terms shows an EP message passing algorithm is equivalent to GAMP and to AMP for AWGN channels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives a concise expectation propagation based message passing algorithm for the general measurement channel. By neglecting some high-order infinitesimal terms, it proves this EP-MPA becomes equivalent to the generalized approximate message passing algorithm. For additive white Gaussian noise channels the same steps further reduce it to standard approximate message passing. The result supplies a single message passing perspective that unifies these algorithms.

Core claim

A concise expectation propagation (EP) based message passing algorithm (MPA) is derived for the general measurement channel. By neglecting some high-order infinitesimal terms, the EP-MPA is proven to be equivalent to the Generalized Approximate Message Passing (GAMP), which exploits central limit theorem and Taylor expansion to simplify the belief propagation process. Furthermore, for additive white gaussian noise measurement channels, EP-MPA is proven to be equivalent to the AMP. Such intrinsic equivalence between EP and GAMP/AMP offers a new insight into GAMP and AMP via a unified message passing rule for non-linear processing, and may provide clues towards building new MPAs in solvingmore

What carries the argument

Expectation propagation message passing algorithm (EP-MPA) reduced to GAMP and AMP by neglecting high-order infinitesimal terms.

Load-bearing premise

Neglecting high-order infinitesimal terms produces a valid and useful equivalence between the derived EP-MPA and GAMP without materially changing the algorithm's behavior on the target problems.

What would settle it

Running the full EP-MPA derivation without dropping terms on a small non-linear measurement problem and checking whether its estimates and iteration counts match those of GAMP to within a small tolerance.

Figures

Figures reproduced from arXiv: 1907.02247 by Chau Yuen, Chongwen Huang, Lei Liu, Ying Li, Yong Liang Guan.

Figure 1
Figure 1. Figure 1: System model: x and z are subjected to an linear function z = Ax, and x and z are subjected to symbol-wise transfer probability functions. arXiv:1907.02247v3 [cs.IT] 10 Jul 2019 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Forney-style factor graph. Edges denote variables, and nodes denote [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: EP-MPA illustration. a-priori message is partly used to improve the estimation and the correlation problem is also avoided. Due to these reasons, EP could have a better performance than EMP [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: MSE comparison between EP-MPA and GAMP for clipped com [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
read the original abstract

A concise expectation propagation (EP) based message passing algorithm (MPA) is derived for the general measurement channel. By neglecting some high-order infinitesimal terms, the EP-MPA is proven to be equivalent to the Generalized Approximate Message Passing (GAMP), which exploits central limit theorem and Taylor expansion to simplify the belief propagation process. Furthermore, for additive white gaussian noise measurement channels, EP-MPA is proven to be equivalent to the AMP. Such intrinsic equivalence between EP and GAMP/AMP offers a new insight into GAMP and AMP via a unified message passing rule for non-linear processing, and may provide clues towards building new MPAs in solving more general non-linear problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript derives a concise expectation propagation (EP) based message passing algorithm (MPA) for general measurement channels. By neglecting high-order infinitesimal terms, it claims to prove that this EP-MPA is equivalent to the Generalized Approximate Message Passing (GAMP) algorithm, which uses the central limit theorem and Taylor expansion. For additive white Gaussian noise (AWGN) channels, it further claims equivalence to AMP. The paper positions this as offering a new insight into GAMP and AMP via a unified message passing rule.

Significance. If the equivalence holds with the neglected terms properly justified, the result would unify EP and GAMP/AMP frameworks, providing a message-passing perspective that could facilitate extensions to more general non-linear problems. The derivation from EP toward GAMP/AMP avoids circularity in the abstract.

major comments (1)
  1. [Abstract] The central equivalence claim rests on neglecting 'high-order infinitesimal terms' without specifying which terms (e.g., in expectation or variance updates), providing an error bound, or showing they vanish as o(1/N) in the large-system limit that justifies GAMP's CLT steps. This omission is load-bearing because the equivalence is presented as exact after neglect, yet the effect on fixed points and convergence is unverified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive comments. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract] The central equivalence claim rests on neglecting 'high-order infinitesimal terms' without specifying which terms (e.g., in expectation or variance updates), providing an error bound, or showing they vanish as o(1/N) in the large-system limit that justifies GAMP's CLT steps. This omission is load-bearing because the equivalence is presented as exact after neglect, yet the effect on fixed points and convergence is unverified.

    Authors: We agree that the manuscript would be strengthened by explicitly identifying the neglected terms and their asymptotic order. These terms arise in the moment-matching steps of the EP message updates for the means and variances when approximating the outgoing messages. We will revise the derivation to specify the terms, show they are o(1/N) under the large-system limit with fixed ratio M/N, and note consistency with the CLT underlying GAMP. The fixed points coincide asymptotically because the neglected contributions vanish in the limit; we will add a short discussion clarifying this and the implications for convergence. revision: yes

Circularity Check

0 steps flagged

No circularity: forward derivation from EP-MPA to GAMP/AMP via explicit approximation

full rationale

The paper starts from an EP-based message passing derivation for general channels, then applies an explicit (if unquantified) neglect of high-order infinitesimal terms to reach equivalence with GAMP, and similarly for AMP under AWGN. This is a one-directional reduction from the EP starting point rather than any self-definitional loop, fitted parameter renamed as prediction, or load-bearing self-citation. No equations are shown to reduce to their own inputs by construction, and the central claim does not import uniqueness theorems or ansatzes from the authors' prior work. The derivation remains self-contained against the external GAMP literature.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim depends on the validity of dropping high-order infinitesimal terms and on the applicability of the central limit theorem plus Taylor expansion inside the message-passing derivation.

axioms (2)
  • domain assumption Neglecting high-order infinitesimal terms yields a valid equivalence between EP-MPA and GAMP
    Explicitly invoked in the abstract as the step that establishes equivalence to GAMP.
  • domain assumption Central limit theorem and Taylor expansion simplify belief propagation without changing the essential behavior
    Cited in the abstract as the mechanism used by GAMP that the new derivation matches.

pith-pipeline@v0.9.0 · 5638 in / 1282 out tokens · 38420 ms · 2026-05-25T09:26:44.637503+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · 3 internal anchors

  1. [1]

    Generalized approximate message passing for estimation with random linear mixing,

    S. Rangan, “Generalized approximate message passing for estimation with random linear mixing,” 2011 IEEE ISIT , Petersburg, 2011

    work page 2011

  2. [2]

    Generalized approximate message passing for estimation with random linear mixing,

    S. Rangan, “Generalized approximate message passing for estimation with random linear mixing,” preprint, 2010

    work page 2010

  3. [3]

    Message passing algo- rithms for compressed sensing,

    D. L. Donoho, A. Maleki, and A. Montanari, “Message passing algo- rithms for compressed sensing,” Proceedings of the National Academy of Sciences, 2009

    work page 2009

  4. [4]

    An AMP based decoder for massive MU-MIMO-OFDM with low-resolution ADCs,

    Chen Cao, Hongxiang Li and Zixia Hu, “An AMP based decoder for massive MU-MIMO-OFDM with low-resolution ADCs,” 2017 ICNC, Santa Clara, CA, 2017, pp. 449-453

    work page 2017

  5. [5]

    Beam-on-graph: simul- taneous channel estimation for mmWave MIMO systems with multiple users,

    M. Kokshoorn, H. Chen, Y . Li and B. Vucetic, “Beam-on-graph: simul- taneous channel estimation for mmWave MIMO systems with multiple users,” IEEE Trans. Commun., vol. 66, no. 7, pp. 2931-2946, July 2018

    work page 2018

  6. [6]

    Generalized Approximate Message Passing Aided Frequency Domain Turbo Equalizer for Single-Carrier Spatial Modulation,

    Y . Zhao, Y . Xiao, P. Yang, B. Dong, R. Shi and K. Deng, “Generalized Approximate Message Passing Aided Frequency Domain Turbo Equalizer for Single-Carrier Spatial Modulation,” IEEE Trans. Vehi. Tech., vol. 67, no. 4, pp. 3630-3634, April 2018

    work page 2018

  7. [7]

    Generalized approximate message- passing decoder for universal sparse superposition codes,

    E. Biyik, J. Barbier and M. Dia, “Generalized approximate message- passing decoder for universal sparse superposition codes,” 2017 IEEE ISIT, Aachen, 2017, pp. 1593-1597

    work page 2017

  8. [8]

    Massive connectivity with massive MIMO-part I: device activity detection and channel estimation,

    L. Liu and W. Yu, “Massive connectivity with massive MIMO-part I: device activity detection and channel estimation,” IEEE Trans. Sign. Proc., vol. 66, no. 11, pp. 2933-2946, June, 2018

    work page 2018

  9. [9]

    BM3D-AMP: A new image recovery algorithm based on BM3D denoising,

    C. A. Metzler, A. Maleki and R. G. Baraniuk, “BM3D-AMP: A new image recovery algorithm based on BM3D denoising,” 2015 IEEE ICIP , Quebec City, QC, 2015, pp. 3116-3120

    work page 2015

  10. [10]

    Two-dimensional pattern-coupled sparse bayesian learning via generalized approximate message passing,

    J. Fang, L. Zhang and H. Li, “Two-dimensional pattern-coupled sparse bayesian learning via generalized approximate message passing,” IEEE Trans. Image Proc., vol. 25, no. 6, pp. 2920-2930, June 2016

    work page 2016

  11. [11]

    Low-rank spatial channel estimation for millimeter wave cellular systems,

    P. A. Eliasi, S. Rangan and T. S. Rappaport, “Low-rank spatial channel estimation for millimeter wave cellular systems,” IEEE Trans. Wireless Commun., vol. 16, no. 5, pp. 2748-2759, May 2017

    work page 2017

  12. [12]

    A family of algorithms for approximate Bayesian inference,

    T. Minka, “A family of algorithms for approximate Bayesian inference,” Ph.D. dissertation, Mass. Inst. Technol. , Cambridge, MA, USA, 2001

    work page 2001

  13. [13]

    Expectation consistent approximate infer- ence,

    M. Opper and O. Winther, “Expectation consistent approximate infer- ence,” Journal of Machine Learning Research, vol. 6, no. Dec, pp. 2177– 2204, 2005

    work page 2005

  14. [14]

    Gaussian message passing on linear models: an update,

    H. A. Loeliger, J. Hu, S. Korl, Q. Guo, and L. Ping, “Gaussian message passing on linear models: an update,” Int. Symp. on Turbo codes and Related Topics, Apr. 2006

    work page 2006

  15. [15]

    Convergence analysis and assurance for Gaussian message passing iterative detector in massive MU-MIMO systems,

    L. Liu, C. Yuen, Y . L. Guan, Y . Li, and Y . Su, “Convergence analysis and assurance for Gaussian message passing iterative detector in massive MU-MIMO systems,” IEEE Trans. Wireless Commun., 15 (9), 6487-6501, Sept. 2016

    work page 2016

  16. [16]

    Gaussian Message Passing for Overloaded Massive MIMO-NOMA,

    L. Liu, C. Yuen, Y . L. Guan, Y . Li and C. Huang, “Gaussian Message Passing for Overloaded Massive MIMO-NOMA,” IEEE Trans. Wireless Commun., vol. 18, no. 1, pp. 210-226, Jan. 2019

    work page 2019

  17. [17]

    Capacity-achieving MIMO- NOMA: iterative LMMSE detection,

    L. Liu, C. Yuen, Y . L. Guan, and Y . Li, “Capacity-achieving MIMO- NOMA: iterative LMMSE detection,” IEEE Trans. Signal Process. , vol. 67, no. 7, 1758–1773, April 2019

    work page 2019

  18. [18]

    Practical MIMO-NOMA: Low Complexity and Capacity-Approaching Solution,

    Y . Chi, L. Liu, G. Song, C. Yuen, Y . L. Guan and Y . Li, “Practical MIMO-NOMA: Low Complexity and Capacity-Approaching Solution,” IEEE Trans. Wireless Commun. , vol. 17, no. 9, pp. 6251-6264, Sept. 2018

    work page 2018

  19. [19]

    S-AMP: Approximate message passing for general matrix ensembles,

    B. Cakmak, O. Winther, and B. H. Fleury, “S-AMP: Approximate message passing for general matrix ensembles,” 2014 IEEE ITW , Nov. 2014, pp. 192-196

    work page 2014

  20. [20]

    Ap- proximate inference techniques with expectation constraints,

    T. Heskes, M. Opper, W. Wiegerinck, O. Winther, and O. Zoeter, “Ap- proximate inference techniques with expectation constraints,” J. Statist. Mech., no. P11-15, Nov. 2005

    work page 2005

  21. [21]

    Low-complexity iterative detection for large-scale multiuser MIMO-OFDM systems using approximate message passing,

    S. Wu, L. Kuang, Z. Ni, J. Lu, D. Huang, and Q. Guo, “Low-complexity iterative detection for large-scale multiuser MIMO-OFDM systems using approximate message passing,” IEEE J. Sel. Topics Signal Process. , vol. 8, no. 5, pp. 902-915, Oct. 2014

    work page 2014

  22. [22]

    Orthogonal AMP,

    J. Ma and L. Ping, “Orthogonal AMP,” IEEE Access, vol. 5, pp. 2020- 2033, 2017

    work page 2020

  23. [23]

    Vector Approximate Message Passing

    S. Rangan, P. Schniter, and A. Fletcher, “Vector approximate message passing,” arXiv preprint arXiv:1610.03082 , 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  24. [24]

    Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements

    K. Takeuchi, “Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariant measurements,” arXiv preprint arXiv:1701.05284, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  25. [25]

    An expectation propagation perspective on approximate message passing,

    X. Meng, S. Wu, L. Kuang and J. Lu, “An expectation propagation perspective on approximate message passing,” IEEE Sign. Proc. Letters , vol. 22, no. 8, pp. 1194-1197, Aug. 2015

    work page 2015

  26. [26]

    A unified Bayesian inference framework for generalized linear models,

    X. Meng, S. Wu and J. Zhu, “A unified Bayesian inference framework for generalized linear models,” IEEE Sign. Proc. Letters , vol. 25, no. 3, pp. 398-402, 2018

    work page 2018

  27. [27]

    Bilinear adaptive generalized vector approximate message passing,

    X. Meng and J. Zhu, “Bilinear adaptive generalized vector approximate message passing,” IEEE Access, vo. 7, pp. 4807-4815, 2018

    work page 2018

  28. [28]

    Concise derivation for generalized approximate message passing using expectation propagation,

    Q. Zou, H. Zhang, C. K. Wen, S. Jin, and R. Yu, “Concise derivation for generalized approximate message passing using expectation propagation,” IEEE Signal Process. Lett. , vol. 25, no. 12, pp. 1835-1839, 2018

    work page 2018

  29. [29]

    A comment on the "A unified Bayesian inference framework for generalized linear models"

    J. Zhu, “A comment on the ’A unified Bayesian inference framework for generalized linear models’” arXiv preprint arXiv:1904.04485, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1904

  30. [30]

    Iterative Detection in Coded Linear Systems Based on Orthogonal AMP,

    J. Ma, L. Liu, X. Yuan, and L. Ping, “Iterative Detection in Coded Linear Systems Based on Orthogonal AMP,” 2018 IEEE ISTC, Hong Kong, Dec 2018

    work page 2018

  31. [31]

    Capacity Optimality of AMP in Coded Systems,

    L. Liu, C. Liang, J. Ma, and L. Ping “Capacity Optimality of AMP in Coded Systems,” arXiv preprint arXiv:1901.09559, 2019

    work page arXiv 1901

  32. [32]

    Expectation Propagation Detection for High-Order High-Dimensional MIMO Systems,

    J. Cespedes, P. M. Olmos, M. Sanchez-Fernandez and F. Perez-Cruz, “Expectation Propagation Detection for High-Order High-Dimensional MIMO Systems,” IEEE Trans. Commun. , vol. 62, no. 8, pp. 2840-2849, Aug. 2014

    work page 2014