Generalized approximate message passing for estimation with random linear mixing

Sundeep Rangan

doi:10.1109/ISIT.2011.6033942

Generalized approximate message passing for estimation with random linear mixing

Sundeep Rangan

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages	2168-2172
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2011.6033942
State	Published - 2011
Event	2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation Duration: Jul 31 2011 → Aug 5 2011

Publication series

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

Other

Other	2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Country/Territory	Russian Federation
City	St. Petersburg
Period	7/31/11 → 8/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

Access to Document

10.1109/ISIT.2011.6033942

Cite this

Rangan, S 2011, Generalized approximate message passing for estimation with random linear mixing. in 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011., 6033942, IEEE International Symposium on Information Theory - Proceedings, pp. 2168-2172, 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011, St. Petersburg, Russian Federation, 7/31/11. https://doi.org/10.1109/ISIT.2011.6033942

@inproceedings{3ae817facb82400188578c5aca975cf8,

title = "Generalized approximate message passing for estimation with random linear mixing",

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.",

keywords = "Optimization, belief propagation, compressed sensing, estimation, random matrices",

author = "Sundeep Rangan",

year = "2011",

doi = "10.1109/ISIT.2011.6033942",

language = "English (US)",

isbn = "9781457705953",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "2168--2172",

booktitle = "2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011",

note = "2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 ; Conference date: 31-07-2011 Through 05-08-2011",

}

TY - GEN

T1 - Generalized approximate message passing for estimation with random linear mixing

AU - Rangan, Sundeep

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Optimization

KW - belief propagation

KW - compressed sensing

KW - estimation

KW - random matrices

UR - http://www.scopus.com/inward/record.url?scp=80054799706&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80054799706&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2011.6033942

DO - 10.1109/ISIT.2011.6033942

M3 - Conference contribution

AN - SCOPUS:80054799706

SN - 9781457705953

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2168

EP - 2172

BT - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

T2 - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

Y2 - 31 July 2011 through 5 August 2011

ER -

Generalized approximate message passing for estimation with random linear mixing

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this