Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Sampling from Gaussian Graphical Models by Subgraph Correction

Ying Liu

Generating exact or accurate samples is a basic and fundamental operation in Gaussian graphical models. Commonly used algorithms, such as Cholesky decomposition, forward sampling, and Gibbs sampling, have various limitations. In this talk, we first observe the relationship between Gibbs sampling and Gauss-Seidel iteration. We then propose a general framework in which many existing iterative algorithms for solving linear systems can be converted to corresponding sampling algorithms. In particular, we discuss the sampling algorithm corresponding to the(generalized) embedded tree algorithm, where a graph with cycles is decomposed into a tractable subgraph and a set of residual edges. This sampling algorithm proceeds at each step by generating an independent sample from the tractable subgraph followed by adding a random correction term to compensate for residual edges.

Problems with this site should be emailed to