Degree-M Bethe and Sinkhorn permanent based bounds on the permanent of a non-negative matrix
Other outputs

Altmetrics Information
.

Other information
AbstractThe 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 is 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 infinity, 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.
All Author(s) ListYuwen Huang, Navin Kashyap, Pascal O. Vontobel
Title of Publicationarxiv, Computing Research Repository (CoRR)
Year2023
Pages1 - 17
LanguagesEnglish-United States

Last updated on 2024-03-01 at 09:20