2023/06/04 by Yuwen Huang, Huang, Yuwen, Kashyap, Navin +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Information Theory (cs.IT) #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2306.02280
openalex publication_date 2023/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 → ∞, 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.