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

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

2009-11-08

arxiv.org/abs/0911.1419v2

Computer Science

Data Structures and Algorithms

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

Scientific paper

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}(\beta_i^j(1-\beta_i^j))/\prod_{i,j}(1-\beta_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.

Affiliated with

Also associated with

No associations

Rating

Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-685853