2005/04/30 by Joris M. Mooij, Hilbert J. Kappen
Computer Science · Mathematics · #Algorithm #Applied mathematics #Belief propagation #Binary number #Combinatorics #Computer science #Contrast (vision) #Convergence (economics) #Cooperative Communication and Network Coding #Discrete mathematics #Error Correcting Code Techniques #Factor graph #Mathematical optimization #Mathematics #Pairwise comparison #Product (mathematics) #Quantum Computing Algorithms and Architecture #Statistics #Variable (mathematics) #cs.AI #cs.IT #math.IT
paper · pdf · doi:10.1109/tit.2007.909166
published as IEEE Transactions on Information Theory, 53(12):4422-4437 Dec. 2007 · 15 pages, 5 figures. Major changes and new results in this revised version. Submitted to IEEE Transactions on Information Theory
arxiv created 2007/05/08 · openalex publication_date 2007/12/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Novel conditions are derived that guarantee convergence of the Sum-Product Algorithm (also known as Loopy Belief Propagation or simply Belief Propagation (BP)) to a unique fixed point, irrespective of the initial messages, for parallel (synchronous) updates. 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. The conditions are compared with existing ones, numerically and, if possible, analytically. For binary variables with pairwise interactions, sufficient conditions are derived 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.