D-CIS Publication Database

Publication

Type of publication:Article
Entered by:JOSM
TitleSufficient Conditions for Convergence of the Sum-Product Algorithm
Bibtex cite ID
Journal IEEE Transactions on Information Theory
Year published 2007
Month December
Volume 53
Number 12
Pages 4422-4437
ISSN 0018-9448
Keywords sufficient conditions,convergence,sum-product,algorithm
Abstract
We derive novel conditions that guarantee convergence of the Sum-Product algorithm (also known as Loopy Belief Propagation or simply Belief Propagation) to a unique fixed point, irrespective of the initial messages. The computational complexity of the conditions is polynomial in the number of variables. In contrast with previously existing conditions, our results are directly applicable to arbitrary factor graphs (with discrete variables) and are shown to be valid also in the case of factors containing zeros, under some additional conditions. We compare our bounds with existing ones, numerically and, if possible, analytically. For binary variables with pairwise interactions, we derive sufficient conditions that take into account local evidence (i.e. single variable factors) and the type of pair interactions (attractive or repulsive). It is shown empirically that this bound outperforms existing bounds.
Authors
Mooij, Joris
Kappen, Hilbert J.
Topics
=SEE CLASSIFICATION DIFFERENCE FROM OTHERS=
BibTeXBibTeX
RISRIS
Attachments
 
Total mark: 5