标题： 度-$M$Bethe 和 Sinkhorn 永久性基于非负矩阵的永久性界 显示英文标题

标题： Degree-$M$ Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-negative Matrix

摘要： 非负方阵的永久式可以通过找到与某些适当定义的因子图相关的Bethe自由能函数的最小值来很好地近似；这种对永久式的近似称为Bethe永久式。 Vontobel通过度数为$M$的Bethe永久式对Bethe永久式给出了组合特性描述，这些度数为$M$的覆盖基于底层因子图。 在本文中，我们证明了基于度数为$M$的Bethe永久式的非负矩阵永久式的下界，这解决了Vontobel在[IEEE Trans. Inf. Theory, Mar. 2013]中提出的猜想。 我们还证明了基于度数为$M$的Bethe永久式的非负矩阵永久式的上界。 在极限$M \to \infty$下，这些下界和上界给出了已知的基于Bethe永久式的非负矩阵永久式的下界和上界。 此外，我们还证明了对于一种称为（缩放）Sinkhorn永久式的永久式近似具有类似的结果。 显示英文摘要

摘要： 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.