Approximating the Permanent with Belief Propagation

Abstract

This work describes a method of approximating matrix permanents efficiently using belief propagation. We formulate a probability distribution whose partition function is exactly the permanent, then use Bethe free energy to approximate this partition function. After deriving some speedups to standard belief propagation, the resulting algorithm requires $(n^2)$ time per iteration. Finally, we demonstrate the advantages of using this approximation.

Cited by in corpus (12)

• Marginal multi-Bernoulli filters: RFS derivation of MHT, JIPDA and association-based MeMBer
• Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
• Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix
• Approximating the Permanent with Fractional Belief Propagation
• Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning
• Graphical model approximations of random finite set filters
• On the Degeneracy of Spin Ice Graphs, and its Estimate via the Bethe Permanent
• Loop Calculus and Bootstrap-Belief Propagation for Perfect Matchings on Arbitrary Graphs
• Bounding the Bethe and the Degree-$M$ Bethe Permanents
• Phase Transitions for the Uniform Distribution in the PML Problem and its Bethe Approximation
• Revisiting Algebra and Complexity of Inference in Graphical Models
• Bethe Learning of Conditional Random Fields via MAP Decoding