Computer Science – Discrete Mathematics
Scientific paper
2011-07-30
Computer Science
Discrete Mathematics
37 pages, 12 figures
Scientific paper
We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze and generalize the Belief Propagation (BP) approach to computing the permanent of a non-negative matrix. Known bounds and conjectures are verified in experiments, and some new theoretical relations, bounds and conjectures are proposed. We introduce a fractional free energy functional parameterized by a scalar parameter $\gamma\in[-1;1]$, where $\gamma=-1$ corresponds to the BP limit and $\gamma=1$ corresponds to the exclusion principle Mean-Field (MF) limit, and show monotonicity and continuity of the functional with $\gamma$. We observe that the optimal value of $\gamma$, where the $\gamma$-parameterized functional is equal to the exact free energy (defined as the minus log of the permanent), lies in the $[-1;0]$ range, with the low and high values from the range producing provable low and upper bounds for the permanent. Our experimental analysis suggests that the optimal $\gamma$ varies for different ensembles considered but it always lies in the $[-1;-1/2]$ interval. Besides, for all ensembles considered the behavior of the optimal $\gamma$ is highly distinctive, thus offering a lot of practical potential for estimating permanents of non-negative matrices via the fractional free energy functional approach.
Chertkov Michael
Yedidia Adam B.
No associations
LandOfFree
Computing the Permanent with Belief Propagation 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 Computing the Permanent with Belief Propagation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the Permanent with Belief Propagation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-136143