Spectral Independence Beyond Uniqueness using the topological method
Spectral Independence Beyond Uniqueness using the topological method
复制标题
DOI：
10.48550/arxiv.2211.03753
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Charilaos Efthymiou
中科院分区：
文献类型：
--
作者：
Charilaos Efthymiou
我们给出了使用[Anari，Liu，Oveis-Gharan：Focs 2020]中新引入的强大的光谱独立性方法来快速混合Glauber动力学的新结果。在我们的结果中，Gibbs分布的参数用$G的邻接矩阵的谱半径或桥本非回溯矩阵的谱半径表示。这一分析依赖于我们引入的新技术来确定两个自旋Gibbs分布的成对影响矩阵的最大本征值。有一个共同的框架支撑着这些技术，我们称之为拓扑法。其思想是系统地利用数学{i}^{\lambda，{tau}_{G}}和称为自回避步行树的拓扑结构之间的众所周知的联系。我们的方法是新颖的，并为建立Gibbs分布的谱独立性问题提供了新的见解。更重要的是，它允许我们在谱半径小于最大度的图的硬核模型和伊辛模型等分布上推导出新的-改进的-Glauber动力学快速混合界。
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}^{\Lambda,\tau}_{G}$ for the two spin Gibbs distribution $\mu$. 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}^{\Lambda,\tau}_{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.