Stochastic Systems Group  

Walksum analysis and convergence of Embedded Subgraph algorithms
Venkat Chandrasekaran
SSG, MIT
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 GaussSeidel, and other hybrid versions of these algorithms. Importantly, we allow our iterations to be nonstationary, i.e. based on an arbitrary sequence of tractable subgraphs. We analyze these iterations using the recently developed walksum interpretation of Gaussian inference. We describe the walks "computed" by our algorithms using walksum diagrams. The convergence of these algorithms follows for walksummable 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 nonstationary algorithm provides a significant speedup in convergence over traditional onetree and twotree 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 walksummable models.
Joint work with Jason Johnson and Alan Willsky.
Problems with this site should be emailed to jonesb@mit.edu