Sampling from Gaussian Markov random fields using stationary and non-stationary subgraph perturbations

Ying Liu, Oliver Kosut, Alan S. Willsky

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Gaussian Markov random fields (GMRFs) or Gaussian graphical models have been widely used in many applications. Efficiently drawing samples from GMRFs has been an important research problem. In this paper, we introduce the subgraph perturbation sampling algorithm, which makes use of any pre-existing tractable inference algorithm for a subgraph by perturbing this algorithm so as to yield asymptotically exact samples for the intended distribution. We study the stationary version where a single fixed subgraph is used in all iterations, as well as the non-stationary version where tractable subgraphs are adaptively selected. The subgraphs used can have any structure for which efficient inference algorithms exist: for example, tree-structured, low tree-width, or having a small feedback vertex set. We present new theoretical results that give convergence guarantees for both stationary and non-stationary graphical splittings. Our experiments using both simulated models and large-scale real models demonstrate that this subgraph perturbation algorithm efficiently yields accurate samples for many graph topologies.

Original languageEnglish (US)
Article number6967838
Pages (from-to)576-589
Number of pages14
JournalIEEE Transactions on Signal Processing
Issue number3
StatePublished - Feb 1 2015


  • Feedback vertex set
  • Gaussian Markov random fields
  • Gaussian graphical models
  • graphical splittings

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Sampling from Gaussian Markov random fields using stationary and non-stationary subgraph perturbations'. Together they form a unique fingerprint.

Cite this