Degree-M Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-Negative Matrix

Yuwen Huang, Navin Kashyap, Pascal O. Vontobel

TL;DR

This paper introduces novel degree-M Bethe and Sinkhorn permanent-based bounds for approximating the permanent of non-negative matrices. These bounds, which become the established Bethe and Sinkhorn permanent bounds in the limit as M approaches infinity, help resolve a conjecture and offer new combinatorial characterizations for these important matrix properties.

What Problem Does This Paper Address?

The permanent of a matrix, a fundamental quantity in combinatorics and theoretical computer science, is notoriously difficult to compute (#P-complete). While approximations like the Bethe permanent and Sinkhorn permanent exist, understanding their relationship to the true permanent, especially through combinatorial means, remains an active research area. Specifically, this paper addresses a conjecture by Vontobel regarding degree-M Bethe permanent-based lower bounds and extends this line of inquiry to provide both lower and upper bounds for both Bethe and Sinkhorn approximations, offering a deeper combinatorial understanding of these approximations.

Methods

The authors leverage the framework of factor graphs and their associated free energy functions to analyze the permanent. They introduce "degree-M" versions of Bethe and Sinkhorn permanents, which are derived from degree-M covers of the underlying factor graph. The core of their contribution lies in proving new lower and upper bounds on the permanent using these degree-M approximations. These bounds are established through a series of lemmas and theorems that involve recursive relationships between coefficients related to these approximations, ultimately connecting them to combinatorial quantities. The paper also utilizes concepts from graph theory, probability mass functions, and algebraic manipulations of factorials and exponents.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Degree-M Bounds as a Bridge: The introduction of degree-M Bethe and Sinkhorn permanents provides a powerful tool to bridge the gap between exact permanents and their approximations. By analyzing these degree-M versions, the authors can derive bounds that are more tractable than direct analysis of the original approximations.
  • Resolving a Conjecture: The paper successfully proves a conjecture proposed by Vontobel concerning degree-M Bethe permanent-based lower bounds, strengthening our understanding of the relationship between these combinatorial quantities.
  • Combinatorial Characterizations: The work provides new combinatorial characterizations for the scaled Sinkhorn permanent, extending the combinatorial insights previously available for the Bethe permanent.
  • Recursive Structure: The discovery of recursive relationships for the coefficients associated with these approximations is a key technical insight, allowing for systematic analysis and bounding.
  • Asymptotic Behavior: The paper highlights that as the degree M goes to infinity, the derived bounds converge to the well-known Bethe and Sinkhorn permanent bounds, validating the approach and connecting it to existing results.

Key Results

  • Degree-M Lower and Upper Bounds: The paper proves degree-M Bethe-permanent-based lower and upper bounds on the permanent of a non-negative matrix.
  • Similar Bounds for Sinkhorn: Analogous degree-M Bethe-permanent-based lower and upper bounds are also established for the scaled Sinkhorn permanent.
  • Asymptotic Convergence: In the limit $M \to \infty$, these degree-M bounds yield the known Bethe-permanent-based and Sinkhorn-permanent-based bounds.
  • Conjecture Resolution: A conjecture proposed by Vontobel in 2013 regarding degree-M Bethe permanent-based lower bounds is solved.
  • Combinatorial Characterizations: New combinatorial characterizations are provided for the scaled Sinkhorn permanent.

Limitations and Future Work

  • Computational Intractability for Finite M: The paper notes that computing degree-M Bethe and Sinkhorn permanents for finite M can be intractable in general.
  • Open Problems: The authors identify several open problems, including finding "more basic" proofs for some of the inequalities established in the paper, proving the inequality $H_G(\gamma) \ge H_B(\gamma)$ for all $\gamma \in \Gamma_n$ without relying on Schrijver's inequality, and finding tighter bounds for certain inequalities.
  • Generalization to Other Factor Graphs: The authors suggest that the techniques used in this paper might be extendable to better understand Bethe approximations for other factor graphs.
  • Extension to Bipartite S-NFGs: Generalizing the results to bipartite S-NFGs with multi-affine homogeneous real stable polynomials, as studied in [35], is proposed as a future research direction.

Summary updated

Abstract

The permanent of a non-negative square matrix can be well approximated by finding the minimum of the Bethe free energy function 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},
}
Figure