Paper Info
Title
Hybrid Generalized Approximate Message Passing With Applications To Structured Sparsity
Abstract
Gaussian and quadratic approximations of message passing algorithms on graphs have attracted considerable attention due to their computational simplicity, analytic tractability, and wide applicability in optimization and statistical inference problems. This paper summarizes 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 each weak edge representing a small, linearizable coupling of variables. AMP approximations based on the central limit theorem can be 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 between 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.
Year
DOI
Venue
2012
10.1109/ISIT.2012.6283054
2012 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT)
Keywords
Field
DocType
belief propagation,message passing,approximation algorithms,graphs,graphical models,approximation theory,graph theory,optimization,vectors,gaussian processes
Graph theory,Approximation algorithm,Combinatorics,Computer science,Approximation theory,Gaussian,Gaussian process,Graphical model,Message passing,Belief propagation
Conference
Citations 
PageRank 
References 
3
0.48
0
Authors
4
Name
Order
Citations
PageRank
Sundeep Rangan13101163.90
Alyson K. Fletcher255241.10
Vivek K. Goyal32031171.16
Philip Schniter4162093.74