Hybrid Approximate Message Passing
Open Access
- 8 June 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 65 (17) , 4577-4592
Abstract
Gaussian and quadratic approximations of message passing algorithms on graphs have attracted considerable recent attention due to their computational simplicity, analytic tractability, and wide applicability in optimization and statistical inference problems. This paper presents a systematic framework for incorporating such approximate message passing (AMP) methods in general graphical models. The key concept is a partition of dependencies of a general graphical model into strong and weak edges, with the weak edges representing small, linearizable couplings of variables. AMP approximations based on the central limit theorem can be readily applied to aggregates of many weak edges and integrated with standard message passing updates on the strong edges. The resulting algorithm, which we call hybrid generalized approximate message passing (HyGAMP), can yield significantly simpler implementations of sum-product and max-sum loopy belief propagation. By varying the partition of strong and weak edges, a performance-complexity tradeoff can be achieved. Group sparsity and multinomial logistic regression problems are studied as examples of the proposed methodology.Keywords
All Related Versions
Funding Information
- National Science Foundation (1116589, 1302336, 1547332, 1254204, 1738286, 1422034, CCF-1527162)
- Office of Naval Research (N00014-15-1-2677)
This publication has 41 references indexed in Scilit:
- Bilinear Generalized Approximate Message Passing—Part I: DerivationIEEE Transactions on Signal Processing, 2014
- Bilinear Generalized Approximate Message Passing—Part II: ApplicationsIEEE Transactions on Signal Processing, 2014
- Graphical models concepts in compressed sensing2012
- The composite absolute penalties family for grouped and hierarchical variable selectionThe Annals of Statistics, 2009
- Message-passing algorithms for compressed sensingProceedings of the National Academy of Sciences of the United States of America, 2009
- The Group Lasso for Logistic RegressionJournal of the Royal Statistical Society Series B: Statistical Methodology, 2008
- An Interior-Point Method for Large-Scale -Regularized Least SquaresIEEE Journal of Selected Topics in Signal Processing, 2007
- Model Selection and Estimation in Regression with Grouped VariablesJournal of the Royal Statistical Society Series B: Statistical Methodology, 2005
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998