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\nmatrix, $P=(P_i^j|i,j=1,\\cdots,N)$, or equivalently the problem of weighted\ncounting of the perfect matchings over the complete bipartite graph $K_{N,N}$.\nThe problem is known to be of likely exponential complexity. Stated as the\npartition function $Z$ of a graphical model, the problem allows exact Loop\nCalculus representation [Chertkov, Chernyak '06] in terms of an interior\nminimum of the Bethe Free Energy functional over non-integer doubly stochastic\nmatrix of marginal beliefs, $\\beta=(\\beta_i^j|i,j=1,\\cdots,N)$, also\ncorrespondent to a fixed point of the iterative message-passing algorithm of\nthe Belief Propagation (BP) type. Our main result is an explicit expression of\nthe exact partition function (permanent) in terms of the matrix of BP\nmarginals, $\\beta$, as $Z=\\mbox{Perm}(P)=Z_{BP}\n\\mbox{Perm}(\\beta_i^j(1-\\beta_i^j))/\\prod_{i,j}(1-\\beta_i^j)$, where $Z_{BP}$\nis the BP expression for the permanent stated explicitly in terms if $\\beta$.\nWe give two derivations of the formula, a direct one based on the Bethe Free\nEnergy and an alternative one combining the Ihara graph-$\\zeta$ function and\nthe Loop Calculus approaches. Assuming that the matrix $\\beta$ of the Belief\nPropagation marginals is calculated, we provide two lower bounds and one\nupper-bound to estimate the multiplicative term. Two complementary lower bounds\nare based on the Gurvits-van der Waerden theorem and on a relation between the\nmodified permanent and determinant respectively.\n