Sufficient conditions for convergence of the 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.

15 pages, 5 figures. Major changes and new results in this revised version. Submitted to IEEE Transactions on Information Theory

References in corpus (5)

• Expectation Propagation for approximate Bayesian inference
• Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
• Survey Propagation as local equilibrium equations
• Approximate Inference and Constrained Optimization
• Sufficient conditions for convergence of Loopy Belief Propagation

Cited by in corpus (35)

• Low-Complexity Detection/Equalization in Large-Dimension MIMO-ISI Channels Using Graphical Models
• Block Models and Personalized PageRank
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• The Bethe Permanent of a Non-Negative Matrix
• Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
• Probabilistic MIMO Symbol Detection with Expectation Consistency Approximate Inference
• High-dimensional macroeconomic forecasting using message passing algorithms
• Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation
• Belief Propagation for Continuous State Spaces: Stochastic Message-Passing with Quantitative Guarantees
• An Iterative Receiver for OFDM With Sparsity-Based Parametric Channel Estimation
• Learning Multiple Belief Propagation Fixed Points for Real Time Inference
• A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
• Loopy Belief Propagation, Bethe Free Energy and Graph Zeta Function
• Inference-Based Distributed Channel Allocation in Wireless Sensor Networks
• Message Error Analysis of Loopy Belief Propagation for the Sum-Product Algorithm
• The Role of Normalization in the Belief Propagation Algorithm
• New Understanding of the Bethe Approximation and the Replica Method
• Exact and approximate inference in graphical models: variable elimination and beyond
• The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
• Factorized Graph Representations for Semi-Supervised Learning from Sparse Data
• Convergence and Accuracy Analysis for A Distributed Static State Estimator based on Gaussian Belief Propagation
• Novel Bounds on Marginal Probabilities
• A belief propagation algorithm based on domain decomposition
• Using Latent Binary Variables for Online Reconstruction of Large Scale Systems
• Fixed Points of Belief Propagation -- An Analysis via Polynomial Homotopy Continuation
• Message-Passing Algorithms and Homology
• Region-based Energy Neural Network for Approximate Inference
• Optimization of the Belief-Propagation Algorithm for Distributed Detection by Linear Data-Fusion Techniques
• Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay
• Concavity of reweighted Kikuchi approximation
• Local stability of Belief Propagation algorithm with multiple fixed points
• Large scale probabilistic available bandwidth estimation
• Stochastic Belief Propagation: A Low-Complexity Alternative to the Sum-Product Algorithm
• Concrete Evaluation of the Random Probing Security
• Bethe Learning of Conditional Random Fields via MAP Decoding