Journal article
Belief propagation, Dykstra's algorithm, and iterated information projections
IEEE transactions on information theory, v 56(8), pp 4114-4128
Aug 2010
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
Belief propagation is shown to be an instance of a hybrid between two projection algorithms in the convex programming literature: Dykstra's algorithm with cyclic Bregman projections and an alternating Bregman projections algorithm. Via this connection, new results concerning the convergence and performance of belief propagation can be proven by exploiting the corresponding literature about the two projections algorithms it hybridizes. In this regard, it is identified that the lack of guaranteed convergence for belief propagation results from the asymmetry of its Bregman divergence by proving that when the associated hybrid projection algorithm generalization is used with a symmetric Bregman divergence, it always converges. Additionally, by characterizing factorizations that are close to acyclic in a manner independent of their girth, a new collection of distributions for which belief propagation is guaranteed to perform well is identified using the new projection algorithm framework
Metrics
Details
- Title
- Belief propagation, Dykstra's algorithm, and iterated information projections
- Creators
- John Mac Laren Walsh - Drexel UniversityPhillip Regalia - Communications, Images et Traitement de l'Information
- Publication Details
- IEEE transactions on information theory, v 56(8), pp 4114-4128
- Publisher
- Institute of Electrical and Electronics Engineers
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:000282001700036
- Scopus ID
- 2-s2.0-77954573464
- Other Identifier
- 991014878040504721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Information Systems
- Computer Science, Theory & Methods
- Engineering, Electrical & Electronic
- Mathematics, Applied