Approximate Message Passing

Approximate message passing (AMP) and its variants are a powerful class of algorithms for linear inverse problems and their generalizations. AMP methods were originally developed for compressed sensing problems of estimating sparse vectors from underdetermined linear measurements. They have now been extended to a wide range of estimation and learning problems including regularized least squares, generalized linear models, matrix completion, dictionary learning and estimation in networks of systems with linear and nonlinear blocks. The key appealing features of the methods are their computational scalability and generality. In addition, in certain large random instances, the performance of the methods can be precisely characterized with testable conditions for Bayes optimality, even in non-convex instances.

Software

  • Vampyre: Python-based software package for AMP-based methods.
  • GAMPmatlab: MATLAB-based software package

Publications

CitationResearch AreasDate
S. Rangan, A. K. Fletcher, V. K. Goyal, E. Byrne and P. Schniter, "Hybrid Approximate Message Passing," in IEEE Transactions on Signal Processing, vol. 65, no. 17, pp. 4577-4592, Sept. 1, 2017.AMP2017/09/01
Rangan, Sundeep, Philip Schniter, and Alyson K. Fletcher, Vector approximate message passing, to appear IEEE ISIT, July 2017.AMP2017/07/01
M. Borgerding; P. Schniter; S. Rangan, "AMP-Inspired Deep Networks for Sparse Linear Inverse Problems," in IEEE Transactions on Signal Processing , vol. 65, no. 16, pp. 4293-4308,AMP2017/05/25
S. Rangan, A. K. Fletcher, P. Schniter and U. S. Kamilov, "Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization," in IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 676-697, Jan. 2017.AMP2017/01/01
S. Rangan, P. Schniter, E. Riegler, A. K. Fletcher, V. Cevher, “Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices,” in IEEE Transactions on Information Theory, vol. 62, no. 12, pp. 7464-7474, Dec. 2016. AMP2016/12/02
A. Fletcher, M. Sahraee-Ardakan, S. Rangan, P. Schniter, Expectation Consistent Approximate Inference: Generalizations and Convergence2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, 2016, pp. 190-194. AMP2016/07/15
P. Schniter, S. Rangan and A. K. Fletcher, "Vector approximate message passing for the generalized linear model," Proc. IEEE Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 2016, pp. 1525-1529.AMP2016/04/26
P. Schniter and S. Rangan, "Compressive Phase Retrieval via Generalized Approximate Message Passing," in IEEE Transactions on Signal Processing, vol. 63, no. 4, pp. 1043-1055, Feb.15, 2015. AMP2015/02/15
J. Vila, P. Schniter, S. Rangan, F. Krzakala and L. Zdeborová, "Adaptive damping and mean removal for the generalized approximate message passing algorithm," 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), South Brisbane, QLD, 2015, pp. 2021-2025. AMP2015/01/01
M. Borgerding, P. Schniter, J. Vila and S. Rangan, "Generalized approximate message passing for cosparse analysis compressive sensing," 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), South Brisbane, QLD, 2015, pp. 3756-3760.AMP2015/01/01
S. Rangan, A. K. Fletcher, P. Schniter and U. S. Kamilov, "Inference for Generalized Linear Models via alternating directions and Bethe Free Energy minimization," 2015 IEEE International Symposium on Information Theory (ISIT), Hong Kong, 2015, pp. 1640-1644.AMP2015/01/01
U.S. Kamilov, S. Rangan, A.K. Fletcher, M. Unser, “Approximate Message Passing with Consistent Parameter Estimation and Applications to Sparse Learning,” IEEE Trans. Information Theory, vol. 60, no. 5, pp. 2969-2985, May 2014.AMP2014/05/19
S. Rangan, P. Schniter, A. K. Fletcher, “On the Convergence of Approximate Message Passing with Arbitrary Matrices” P2014 IEEE International Symposium on Information Theory, Honolulu, HI, 2014, pp. 236-240.AMP2014/02/13
A. K. Fletcher and S. Rangan "Scalable inference for neuronal connectivity from calcium imaging." Advances in Neural Information Processing Systems. 2014.AMP2014/01/01
S. Rangan, P. Schniter, E. Riegler, A. Fletcher and V. Cevher, "Fixed points of generalized approximate message passing with arbitrary matrices," 2013 IEEE International Symposium on Information Theory, Istanbul, 2013, pp. 664-668.AMP2013/01/01
U. S. Kamilov, V. K. Goyal and S. Rangan, "Message-Passing De-Quantization With Applications to Compressed Sensing," in IEEE Transactions on Signal Processing, vol. 60, no. 12, pp. 6270-6281, Dec. 2012.AMP2012/12/01
P. Schniter and S. Rangan, "Compressive phase retrieval via generalized approximate message passing," Proc. 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, 2012, pp. 815-822, October 2012AMP2012/10/01
S. Rangan, A. K. Fletcher, V. K. Goyal and P. Schniter, "Hybrid generalized approximate message passing with applications to structured sparsity," Proc. IEEE Int. Symp. Information Theory (ISIT), Cambridge, MA, pp. 1236-1240, July 2012.AMP2012/07/01
S. Rangan, A.K. Fletcher, “Iterative Estimation of Constrained Rank-One Matrices in Noise” Proc. IEEE Int. Symp. Information Theory (ISIT), Cambridge, MA, pp. 1246-1250, July 2012.AMP2012/07/01
S. Rangan, A.K. Fletcher, V.K. Goyal, “Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing,” IEEE Trans. Information Theory, vol. 58, no.3, pp. 1902–1923, March 2012.AMP2012/03/08
U.S. Kamilov, V.K. Goyal, S. Rangan, “Generalized Approximate Message Passing Estimation from Quantized Samples,” Proc. 4th IEEE Int. Workshop on Computational Advances in Multi-Sensor Adapative Processing (CAMSAP), San Juan, Puerto Rico, pp. 401{404, December 2011.AMP2011/12/01
S. Rangan, “Generalized Approximate Message Passing for Estimation with Random Linear Mixing,” 2011 IEEE International Symposium on Information Theory Proceedings, St. Petersburg, pp. 2168-2172, July-August 2011. AMP2011/07/31
U. Kamilov, V. K. Goyal, and S. Rangan, "Message-Passing Estimation from Quantized Samples," Proc. 4th Workshop on Signal Process. with Adaptive Sparse Structured Representations (SPARS), Edinburgh, United Kingdom, p. 58, June 2011.AMP2011/07/01
U.S. Kamilov, V.K. Goyal, S. Rangan, “Optimal Quantization for Compressive Sensing Under Message Passing Reconstruction,” Proc. IEEE Int. Symp. Information Theory, St. Petersburg, Russia, pp.459-463, Aug. 2011.AMP2011/03/14
S. Rangan, A. K. Fletcher and V. K. Goyal, "Extension of replica analysis to MAP estimation with applications to compressed sensing," Proc. IEEE Int. Symp. Information Theory (ISIT), Austin, TX, pp. 459-463, June 2010./span>AMP2010/06/01