Dual normal factor graphs give faster Gibbs sampling with universal convergence rates

Gibbs sampling is a workhorse for Bayesian inference, but its convergence can be painfully slow for Gaussian graphical models with strong correlations. In a new arXiv paper, researchers Borna Khodabandeh and Mehdi Molkaraie show that moving to the dual domain — obtained by applying a Fourier transform to the local factors of the normal factor graph — dramatically accelerates random-sweep Gibbs sampling. They derive exact convergence rates for homogeneous k-regular graphs in both the primal and dual domains, and prove a remarkable result: for all homogeneous models whose graphs contain cycles, the dual-domain convergence rate is universal, independent of the underlying graph topology. That means the speedup is not lucky coincidence; it is structural.

Even better, the effective convergence rate in the dual domain is governed by the graph's algebraic connectivity — a spectral property that adds an extra layer of acceleration without increasing the computational complexity per sweep. The authors also establish an explicit algebraic relation between covariance structures of the primal and dual models, so practitioners can recover marginal statistics of the original model directly from dual-domain samples. Numerical experiments across several graph families confirm the theory, showing substantial convergence improvements. For machine learning and statistics workflows that rely on MCMC for large graphical models, this dual-domain trick could translate into orders-of-magnitude faster inference — or equivalently, more accurate posterior estimates for the same compute budget.