Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix

Abstract

We consider computation of permanent of a positive $(N\times N)$ non-negative matrix, $P=(P_i^j|i,j=1,\cdots ,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 exact Loop Calculus representation [Chertkov, Chernyak '06] in terms of an interior minimum of the Bethe Free Energy functional over non-integer doubly stochastic matrix of marginal beliefs, $\beta =({\beta }_i^j|i,j=1,\cdots ,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, $\beta$, as $Z=\mbox{Perm}(P)=Z_{BP} \mbox{Perm}(β_i^j(1-β_i^j))/\prod_{i,j}(1-β_i^j)$, where $Z_{BP}$ is the BP expression for the permanent stated explicitly in terms if $\beta$. We give two derivations of the formula, a direct one based on the Bethe Free Energy and an alternative one combining the Ihara graph-$\zeta$ function and the Loop Calculus approaches. Assuming that the matrix $\beta$ of the Belief Propagation 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.

11 pages; submitted to Journal of Physics A: Mathematical Theoretical

References in corpus (4)

• Loop series for discrete statistical models on graphs
• Inference in particle tracking experiments by passing messages between images
• Approximating the Permanent with Belief Propagation
• Belief Propagation and Beyond for Particle Tracking

Cited by in corpus (8)

• The Bethe Permanent of a Non-Negative Matrix
• Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
• An efficient tree decomposition method for permanents and mixed discriminants
• Approximating the Permanent with Fractional Belief Propagation
• New Understanding of the Bethe Approximation and the Replica Method
• Loop Calculus and Bootstrap-Belief Propagation for Perfect Matchings on Arbitrary Graphs
• Approximating the Bethe partition function
• On Convex Programming Relaxations for the Permanent