Accelerated Random-Sweep Gibbs Sampling for Gaussian Graphical Models via Dual Normal Factor Graphs
Convergence of random-sweep Gibbs sampling is significantly accelerated in the dual of a Gaussian graphical model, with exact rates and algebraic structure derived analytically.
Authors: Borna Khodabandeh, Mehdi Molkaraie
Venue: Preprint (to be submitted to IEEE Transactions on Information Theory)
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, the effective convergence rate in the dual domain is governed by the algebraic connectivity of the graph, providing 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. Numerical experiments on several graph families confirm our theoretical results and demonstrate substantial improvements in convergence rates across various settings.
