Sufficient conditions for convergence of the Sum-Product Algorithm

Simple item page
dc.creatorMooij, Joris M.
dc.creatorKappen, Hilbert J.
dc.date2005-04-08
dc.date2007-05-08
dc.date.accessioned2026-07-07T08:49:45Z
dc.date.available2026-07-07T08:49:45Z
dc.descriptionWe 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.
dc.description15 pages, 5 figures. Major changes and new results in this revised version. Submitted to IEEE Transactions on Information Theory
dc.identifierhttps://arxiv.org/abs/cs/0504030
dc.identifierhttp://arxiv.org/abs/cs/0504030
dc.identifierIEEE Transactions on Information Theory, 53(12):4422-4437 Dec. 2007
dc.identifierdoi:10.1109/TIT.2007.909166
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/144412
dc.subjectInformation Theory
dc.subjectArtificial Intelligence
dc.subjectI.2.3; F.2.1
dc.titleSufficient conditions for convergence of the Sum-Product Algorithm
dc.typetext

Files

Collections

arXiv