Computer Science – Information Theory
Scientific paper
2005-04-08
IEEE Transactions on Information Theory, 53(12):4422-4437 Dec. 2007
Computer Science
Information Theory
15 pages, 5 figures. Major changes and new results in this revised version. Submitted to IEEE Transactions on Information Theo
Scientific paper
10.1109/TIT.2007.909166
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.
Kappen Hilbert J.
Mooij Joris M.
No associations
LandOfFree
Sufficient conditions for convergence of the Sum-Product Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sufficient conditions for convergence of the Sum-Product Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sufficient conditions for convergence of the Sum-Product Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-683225