通过傅里叶变换加速高斯图模型的吉布斯采样,收敛更快且不增加计算量。
Accelerated Random-Sweep Gibbs Sampling for Gaussian Graphical Models via Dual Normal Factor Graphs

- 在对偶域中利用傅里叶变换重构因子图,提升采样效率。
- 对称k-正则图下收敛率明确,且对含环图具有统一收敛速度。
- 可直接从对偶模型恢复原始模型边缘统计,适合大规模图推断。
我们研究了带有薄膜先验的高斯图模型中随机扫掠吉布斯采样的收敛性。通过将表示原模型的正态因子图的局部因子进行傅里叶变换,构建对偶模型,发现吉布斯采样的收敛速率显著加快。在两个域中,我们推导出同质k-正则图的精确收敛速率。证明对于所有包含环的同质模型,对偶域中的收敛速率是普适的,与图拓扑无关。此外,我们表明对偶域的有效收敛速率由图的代数连通性决定,实现额外加速而无需增加每次扫描的计算复杂度。我们进一步建立了原模型与对偶模型协方差结构之间的显式代数关系,使得原模型的边缘统计可直接从对偶模型中恢复。多个图族的数值实验验证了理论结果,并在各种设置下展示了显著的收敛速率提升。
原文摘要 · Abstract (English)
We study the convergence properties of the random-sweep Gibbs sampler for Gaussian graphical models with a thin-membrane prior. We demonstrate that the convergence rate of the Gibbs sampler is significantly accelerated in the dual model, which is obtained by applying the Fourier transform to the local factors of the normal factor graph representing the original model. In both domains, we derive the exact convergence rates for homogeneous $k$-regular graphs. We prove that, for all homogeneous models whose graphical representations contain cycles, the convergence rate in the dual domain is universal and independent of the underlying graph topology. Moreover, we show that the effective convergence rate in the dual domain is governed by the algebraic connectivity of the graph, providing an additional acceleration without increasing the computational complexity per sweep. We further establish an explicit algebraic relation between the covariance structures of the primal and dual models, enabling marginal statistics of the primal model to be recovered directly from those of the dual model. Finally, numerical experiments on several graph families confirm our theoretical results and demonstrate substantial improvements in the convergence rates in various settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。