Belief propagation and loop calculus for the permanent of a non-negative matrix
Yusuke Watanabe, Michael Chertkov · Journal of Physics A Mathematical and Theoretical · 2010
We consider computation of the permanent of a positive (N × N) non-negative matrix, P = P j i i, j = 1, . . ., N , or equivalently the problem of weighted counting of the perfect matchings over the complete bipartite graph K N,N .The problem is known to be of likely exponential complexity.Stated as the partition function Z of a graphical model, the problem allows for exact loop calculus representation (Chertkov M and Chernyak V 2006 Phys.Rev. E 72 065102) in terms of an interior minimum of the Bethe free energy functional over non-integer doubly stochastic matrix of marginal beliefs, β = β j i i, j = 1, . . ., N , also correspondent to a fixed point of the iterative message-passing algorithm of the belief propagation (BP) type.Our main result is an explicit expression of the exact partition function (permanent) in terms of the matrix of BP marginals, β, as Z = Perm(P ) = Z BP Perm β j i 1β j i i,j 1β j i , where Z BP is the BP expression for the permanent stated explicitly in terms of β.We give two derivations of the formula, a direct one based on the Bethe free energy and an alternative one combining the Ihara graph-ζ function and the loop calculus approaches.Assuming that the matrix β of the BP marginals is calculated, we provide two lower bounds and one upper bound to estimate the multiplicative term.Two complementary lower bounds are based on the Gurvits-van der Waerden theorem and on a relation between the modified permanent and determinant, respectively.