Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2008 | Published
Journal Article Open

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 sophisticated 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 ldquocomputedrdquo by the algorithms using walk-sum diagrams, and show that for iterations based on a very large and flexible set of sequences of subgraphs, convergence is guaranteed in walk-summable models. Consequently, 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 nonstationary algorithms provide a significant speedup in convergence over traditional one-tree and two-tree iterations.

Additional Information

© 2008 IEEE. Manuscript received January 17, 2007; revised June 15, 2007. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Manuel Davy. This work was supported by the Army Research Office Grant W911NF-05-1-0207 and the Air Force Office of Scientific Research Grant FA9550-04-1-0351. The authors would like to thank Dr. E. Sudderth for helpful discussions and comments on early drafts of this work.

Attached Files

Published - cjw_et_sp08.pdf


Files (568.2 kB)
Name Size Download all
568.2 kB Preview Download

Additional details

August 22, 2023
October 19, 2023