Bounding the permanent of a non-negative matrix via its degree-M Bethe and Sinkhorn permanents
Refereed conference paper presented and published in conference proceedings


Full Text

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, Pascal O. Vontobel
Name of ConferenceIEEE International Symposium on Information Theory
Start Date of Conference25/06/2023
End Date of Conference30/06/2023
Place of ConferenceTaipei
Country/Region of ConferenceTaiwan
Year2023
Month6
PublisherIEEE Information Theory Society
Pages2774 - 2779
LanguagesEnglish-United States

Last updated on 2023-14-09 at 15:32