2009 · 54 citations · 19 references
Open access
Natural SciencesComputer ScienceMathematicsAlgorithmsOptimizationTheory Of ComputationDirected Acyclic GraphsGraph TheoryStatistical MechanicsBelief PropagationLocal Energy MinimaLocal StabilityPositive Definite FunctionsRandom Graph Theory
We propose a new approach to the analysis of Loopy Belief Propagation (LBP) by establishing a formula that connects the Hessian of the Bethe free energy with the edge zeta function. The formula has a number of theoretical implications on LBP. It is applied to give a sufficient condition that the Hessian of the Bethe free energy is positive definite, which shows non-convexity for graphs with multiple cycles. The formula clarifies the relation between the local stability of a fixed point of LBP and local minima of the Bethe free energy. We also propose a new approach to the uniqueness of LBP fixed point, and show various conditions of uniqueness. 1
19
Generalized Belief Propagation
Jonathan S. Yedidia, William T. Freeman, Yair Weiss · 2000 · 916 citations
THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
Hyman Bass · International Journal of Mathematics · 1992 · 434 citations