Generalized approximate message passing for estimation with random linear mixing

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages2168-2172
Number of pages5
DOIs
StatePublished - 2011
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: Jul 31 2011Aug 5 2011

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8104

Other

Other2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
CountryRussian Federation
CitySt. Petersburg
Period7/31/118/5/11

Keywords

  • Optimization
  • belief propagation
  • compressed sensing
  • estimation
  • random matrices

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Generalized approximate message passing for estimation with random linear mixing'. Together they form a unique fingerprint.

Cite this