Estimation in Gaussian Graphical Models using Tractable Subgraphs: A Walk-Sum Analysis

Graphical models provide a powerful formalism for statistical signal processing. Due to their sophis-ticated modeling capabilities, they have found applications in a variety of fields such as computer vision, image processing, and distributed sensor networks. In this paper, we present a general class of algorithms for estimation in Gaussian graphical models with arbitrary structure. These algorithms involve a sequence of inference problems on tractable subgraphs over subsets of variables. This framework includes parallel iterations such as Embedded Trees, serial iterations such as block Gauss-Seidel, and hybrid versions of these iterations. We also discuss a method that uses local memory at each node to overcome temporary communication failures that may arise in distributed sensor network applications. We analyze these algorithms based on the recently developed walk-sum interpretation of Gaussian inference. We describe the walks “computed ” by the algorithms using walk-sum diagrams, and show that arbitrary non-stationary iterations (i.e., based on any sequence of subgraphs) of the algorithms converge in walk-summable models. Since subgraphs can be used in any order, we are free to choose spanning trees and subsets of variables adaptively at each iteration. This leads to efficient methods for optimizing the next iteration step to achieve maximum reduction in error. Simulation results demonstrate that these non-stationary algorithms provide a significant speedup in convergence over traditional one-tree and two-tree iterations