Generalised Approximate Message Passing for Non-I.I.D. Sparse Signals


  • Christian Schou Oxvig
  • Thomas Arildsen


Generalised approximate message passing, non-linear subsequent measurement, Sparse Signals


Generalised approximate message passing (GAMP) is an approximate Bayesian estimation algorithm for signals observed through a linear transform with a possibly non-linear subsequent measurement model. By leveraging prior information about the observed signal, such as sparsity in a known dictionary, GAMP can for example reconstruct signals from underdetermined measurements – known as compressed sensing. In the sparse signal setting, most existing signal priors for GAMP assume the input signal to have i.i.d. entries. Here we present sparse signal priors for GAMP to estimate non-i.d.d. signals through a non-uniform weighting of the input prior, for example allowing GAMP to support model-based compressed sensing.


Sundeep Rangan. “Generalized Approximate Message Passing for Estimation with Random Linear Mixing”. In: IEEE International Symposium on Information Theory (ISIT). St. Petersburg, Russia, July 2011, pp. 2168–2172. DOI: 10.1109/ISIT.2011.6033942.

Sundeep Rangan. “Generalized Approximate Message Passing for Estimation with Random Linear Mixing”. In: arXiv pre-prints (Aug. 2012). arXiv: 1010.5141v2.

E. J. Candès and M. B. Wakin. “An Introduction To Compressive Sampling”. In: IEEE Signal Processing Magazine 25.2 (Mar. 2008), pp. 21–30. DOI: 10.1109/


David L. Donoho, Arian Maleki, and Andrea Montanari. “Message-passing algorithms for compressed sensing”. In: Proceedings of the National Academy of ciences of the United States of America 106.45 (Nov. 2009), pp. 18914–18919. DOI: 10 . 1073 / pnas .0909892106.

T. J. Mitchell and J. J. Beauchamp. “Bayesian Variable Selection in Linear Regression”. In: Journal of the American Statistical Association 83.404 (1988), pp. 1023–1032. DOI: 10.1080/01621459.1988. 10478694.

Jeremy Vila and Philip Schniter. “Expectation Maximization Bernoulli-Gaussian Approximate Message Passing”. In: Forty Fifth Asilomar Conference on Signals, Systems and Computers (ASILOMAR). Pacific Grove, California, USA, Nov. 2011, pp. 799–803. DOI: 10.1109/ACSSC.2011.6190117.

R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde. “Model-Based Compressive Sensing”. In: IEEE Transactions on Information Theory 56.4 (Apr. 2010), pp. 1982–2001. ISSN: 0018-9448. DOI: 10 . 1109 /TIT.2010.2040894.

Justin Ziniel, Sundeep Rangan, and Philip Schniter. “A Generalized Framework for Learning and Recovery of Structured Sparse Signals”. In: IEEE Statistical Signal Processing Workshop (SSP). Ann Arbor, Michigan, USA, Aug. 2012, pp. 325–328. DOI: 10.1109/SSP. 2012.6319694.

Christian Schou Oxvig, Thomas Arildsen, and Torben Larsen. Generalized Approximate Message Passing: Relations and Derivations. Tech. rep. Apr. 2017. DOI: 10.


Florent Krzakala, Marc Mézard, Francois Sausset, Yifan Sun, and Lenka Zdeborová. “Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices”. In: Journal of Statistical Mechanics: Theory and Experiment P08009(Aug. 2012), pp. 1–57. DOI: 10.1088/1742-5468/


Jason T. Parker. “Approximate Message Passing Algorithms for Generalized Bilinear Inference”. PhD thesis. Graduate School of The Ohio State University, 2014.

David Donoho and Jared Tanner. “Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal

processing”. In: Philosophical Transactions of the Royal Society A 367.1906 (Nov. 2009), pp. 4273–4293. DOI: 10.1098/rsta.2009.0152.

Christian Schou Oxvig, Thomas Arildsen, and Torben Larsen. Weighted GAMP Phase Transitions. Sept. 2018. DOI: 10.5281/zenodo.1409655.