论文标题
光谱独立性超出了拓扑方法的唯一性
Spectral Independence Beyond Uniqueness using the topological method
论文作者
论文摘要
我们使用[Anari，Liu，Oveis-Gharan：2020年的新引入且强大的光谱独立性方法提出了新的结果，以快速混合Glauber动力学。在我们的结果中，Gibbs分布的参数是根据$ G $的邻接矩阵的光谱半径或桥本非倒数矩阵的光谱半径表示。分析依赖于我们引入的新技术来绑定成对影响矩阵$ \ MATHCAL {i}^{λ，τ} _ {g} $的最大特征值。有一个共同的框架是这些技术的基础，我们称之为拓扑方法。这个想法是系统地利用$ \ mathcal {i}^{λ，τ} _ {g} $与称为自避免自避免行走树的拓扑结构之间的众所周知的连接。我们的方法是新颖的，并为建立吉布斯分布的光谱独立性的问题提供了新的见解。更重要的是，它使我们能够在分布（例如硬核模型）和图形模型的图形模型中得出新的 - 改进的快速混合边界，即光谱半径小于最大程度。
We present novel results for fast mixing of Glauber dynamics using the newly introduced and powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020]. In our results, the parameters of the Gibbs distribution are expressed in terms of the spectral radius of the adjacency matrix of $G$, or that of the Hashimoto non-backtracking matrix. The analysis relies on new techniques that we introduce to bound the maximum eigenvalue of the pairwise influence matrix $\mathcal{I}^{Λ,τ}_{G}$ for the two spin Gibbs distribution $μ$. There is a common framework that underlies these techniques which we call the topological method. The idea is to systematically exploit the well-known connections between $\mathcal{I}^{Λ,τ}_{G}$ and the topological construction called tree of self-avoiding walks. Our approach is novel and gives new insights to the problem of establishing spectral independence for Gibbs distributions. More importantly, it allows us to derive new -- improved -- rapid mixing bounds for Glauber dynamics on distributions such as the Hard-core model and the Ising model for graphs that the spectral radius is smaller than the maximum degree.
