Approximating the permanent with fractional belief propagation

zbMATH Open1318.65022arXiv1108.0065MaRDI QIDQ2933874FDOQ2933874

Michael Chertkov, Adam B. Yedidia

Publication date: 8 December 2014

Abstract: We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze the Belief Propagation (BP) approach and its Fractional Belief Propagation (FBP) generalization for 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. The Fractional Free Energy (FFE) functional is parameterized by a scalar parameter $gammain[-1;1]$, where $gamma=-1$ corresponds to the BP limit and $gamma=1$ corresponds to the exclusion principle (but ignoring perfect matching constraints) Mean-Field (MF) limit. FFE shows monotonicity and continuity with respect to $gamma$. For every non-negative matrix, we define its special value $gamm{a}_{*}in[-1;0]$ to be the $gamma$ for which the minimum of the $gamma$-parameterized FFE functional is equal to the permanent of the matrix, where the lower and upper bounds of the $gamma$-interval corresponds to respective bounds for the permanent. Our experimental analysis suggests that the distribution of $gamm{a}_{*}$ varies for different ensembles but $gamm{a}_{*}$ always lies within the $[-1;-1/2]$ interval. Moreover, for all ensembles considered the behavior of $gamm{a}_{*}$ is highly distinctive, offering an emprirical practical guidance for estimating permanents of non-negative matrices via the FFE approach.

Full work available at URL: https://arxiv.org/abs/1108.0065

Recommendations

• Belief propagation and loop calculus for the permanent of a non-negative matrix
• Approximating permanents of complex matrices
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Approximating the  -permanent
• Publication:3033320

zbMATH Keywords

graphical modelspermanentbelief propagationexact and approximate algorithmslearning flows

Mathematics Subject Classification ID

Multivariate analysis (62H99)

Cited In (4)

• Gauges, loops, and polynomials for partition functions of graphical models
• A note on a fast breakdown-free algorithm for computing the determinants and the permanents of \(k\)-tridiagonal matrices
• A Tight Analysis of Bethe Approximation for Permanent
• Computing expectations and marginal likelihoods for permutations

This page was built for publication: Approximating the permanent with fractional belief propagation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933874)