Accelerating Gibbs Sampling in Gaussian Graphical Models via Factor-Graph Duality
Exploiting factor-graph duality to transform Gaussian Markov Random Fields into equivalent models with significantly faster Gibbs sampling convergence.
Authors: Borna Khodabandeh, Mehdi Molkaraie
Venue: Manuscript in preparation (to be submitted to IEEE Transactions on Information Theory)
Gibbs sampling is a standard inference method for Gaussian Markov Random Fields (GMRFs), but its convergence rate is highly sensitive to the spectral properties of the precision matrix. On poorly conditioned graphs, mixing can be prohibitively slow.
This work shows that factor-graph duality transformations can be applied to a GMRF to produce an equivalent model — one with the same joint distribution — but whose structure leads to significantly faster Gibbs sampling convergence. The key insight is that the dual model can have better spectral properties for sampling even when the original model does not.
We provide theoretical guarantees on the improvement in convergence rate and demonstrate the effect empirically on several graph families.
