Degree-$M$ Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-negative Matrix
Lists
Only you see this
Abstract
The permanent of a non-negative square matrix can be well approximated by finding the minimum of the Bethe free energy functions associated with some suitably defined factor graph; the resulting approximation to the permanent is called the Bethe permanent. Vontobel gave a combinatorial characterization of the Bethe permanent via degree-$M$ Bethe permanents, which are based on degree-$M$ covers of the underlying factor graph. In this paper, we prove a degree-$M$-Bethe-permanent-based lower bound on the permanent of a non-negative matrix, which solves a conjecture proposed by Vontobel in [IEEE Trans. Inf. Theory, Mar. 2013]. We also prove a degree-$M$-Bethe-permanent-based upper bound on the permanent of a non-negative matrix. In the limit $M \to \infty$, these lower and upper bounds yield known Bethe-permanent-based lower and upper bounds on the permanent of a non-negative matrix. Moreover, we prove similar results for an approximation to the permanent known as the (scaled) Sinkhorn permanent.
BibTeX
@article{huang2024degree,
author = {Yuwen Huang and Navin Kashyap and Pascal O. Vontobel},
title = {{Degree-$M$ Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-negative Matrix}},
journal = {IEEE Transactions on Information Theory},
year = {2024},
url = {https://openreview.net/forum?id=0AgiWIhHL6},
}Loading related content...