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

SSG Seminar Abstract

Walk-sum analysis and convergence of Embedded Subgraph algorithms

Venkat Chandrasekaran

We present a new class of iterative algorithms for inference in Gaussian graphical models that is motivated by the Embedded Trees iteration (ET). Each iteration involves inference on a tractable subgraph. Our framework includes parallel iterations such as ET, serial iterations such as block Gauss-Seidel, and other hybrid versions of these algorithms. Importantly, we allow our iterations to be non-stationary, i.e. based on an arbitrary sequence of tractable subgraphs. We analyze these iterations using the recently developed walk-sum interpretation of Gaussian inference. We describe the walks "computed" by our algorithms using walk-sum diagrams. The convergence of these algorithms follows for walk-summable models.

Since subgraphs can be used in any order, we describe an algorithm that chooses spanning trees adaptively at each iteration. Simulation results demonstrate that this non-stationary algorithm provides a significant speedup in convergence over traditional one-tree and two-tree iterations.

Finally, we describe a method that uses local memory at each node to overcome temporary communication failures that may arise in distributed sensor networks. Under mild conditions, we show that convergence can still be achieved in walk-summable models.

Joint work with Jason Johnson and Alan Willsky.

Problems with this site should be emailed to