Hybrid Approximate Message Passing with Applications to Structured Sparsity
Preprint
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 interactions through aggregates of small, linearizable couplings of variables. AMP approximations based on the Central Limit Theorem can be readily applied to the weak edges and integrated with standard message passing updates on the strong edges. The resulting algorithm, which we call hybrid generalized approximate message passing (Hybrid-GAMP), 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 trade-off can be achieved. Structured sparsity problems are studied as an example of this general methodology where there is a natural partition of edges.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Graphical models concepts in compressed sensing2012
- Convex approaches to model wavelet sparsity patterns2011
- Generalized approximate message passing for estimation with random linear mixing2011
- Estimation with random linear mixing, belief propagation and compressed sensing2010
- Message-passing algorithms for compressed sensingProceedings of the National Academy of Sciences of the United States of America, 2009
- Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse ProblemsIEEE Journal of Selected Topics in Signal Processing, 2007
- An Interior-Point Method for Large-Scale -Regularized Least SquaresIEEE Journal of Selected Topics in Signal Processing, 2007
- Analysis of Belief Propagation for Non-Linear Problems: The Example of CDMA (or: How to Prove Tanaka's Formula)2006
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001