Approximating Permanents of Positive Matrices Using Probabilistic Graphical Models

The basic approach is to create a Pairwise Markov Random Field (PMRF) whose partition function is the permanent of a matrix. The partition function is approximated by minimizing the corresponding Bethe Free Energy of the PMRF. The Bethe Free Energy (BFE) is minimized using the Belief Propagation (BP) algorithm. Since BP does not necessarily converge for arbitrary graphs, I was surprised by the efficiency of BP in computing the Bethe approximation. We extended the algorithm to compute the permanent of rectangular matrices and produced some empirical results.