Bounding the Bethe and the Degree-$M$ Bethe Permanents

Abstract

It was recently conjectured that the permanent of a $P$-lifting ${\theta }^{\uparrow P}$ of a matrix $\theta$ of degree $M$ is less than or equal to the $M$th power of the permanent perm$(\theta )$, i.e., perm$({\theta }^{\uparrow P})\le (\text{perm}(\theta ){)}^M$ and, consequently, that the degree-$M$ Bethe permanent ${\text{perm}}_{M,\mathrm{B}}(\theta )$ of a matrix $\theta$ is less than or equal to the permanent perm$(\theta )$ of $\theta$, i.e., perm${}_{M,\mathrm{B}}(\theta )\le \text{perm}(\theta )$. In this paper, we prove these related conjectures and show in addition a few properties of the permanent of block matrices that are lifts of a matrix. As a corollary, we obtain an alternative proof of the inequality perm${}_{\mathrm{B}}(\theta )\le \text{perm}(\theta )$ on the Bethe permanent of the base matrix $\theta$ that uses only the combinatorial definition of the Bethe permanent.

References in corpus (5)

• The Bethe Partition Function of Log-supermodular Graphical Models
• Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
• Approximating the Permanent with Belief Propagation
• A rigorous proof of the cavity method for counting matchings
• Absdet-Pseudo-Codewords and Perm-Pseudo-Codewords: Definitions and Properties