Abstract: We derive novel suficient conditions for convergence of Loopy Belief Propagation (also
known as the Sum-Product algorithm) to
a unique xed point. Our results improve
upon previously known conditions. For binary variables with (anti-)ferromagnetic interactions, our conditions seem to be sharp.
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