Stochastic Systems Group  

Sampling from Gaussian Graphical Models by Subgraph Correction
Ying Liu
SSG
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 GaussSeidel 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 jonesb@mit.edu