Degree-$M$ Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-negative Matrix
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916263085735936 |
|---|---|
| author | Huang, Yuwen Kashyap, Navin Vontobel, Pascal O. |
| author_facet | Huang, Yuwen Kashyap, Navin Vontobel, Pascal O. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_02280 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Degree-$M$ Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-negative Matrix Huang, Yuwen Kashyap, Navin Vontobel, Pascal O. Combinatorics Information Theory 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. |
| title | Degree-$M$ Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-negative Matrix |
| topic | Combinatorics Information Theory |
| url | https://arxiv.org/abs/2306.02280 |