A Caltech Library Service

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

Chandrasekaran, Venkat and Johnson, Jason K. and Willsky, Alan S. (2008) Estimation in Gaussian Graphical Models Using Tractable Subgraphs: A Walk-Sum Analysis. IEEE Transactions on Signal Processing, 56 (5). pp. 1916-1930. ISSN 1053-587X. doi:10.1109/TSP.2007.912280.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
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.
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-05-1-0207
Air Force Office of Scientific Research (AFOSR)FA9550-04-1-0351
Subject Keywords:distributed estimation; Gauss-Markov random fields; graphical models; maximum walk-sum block; maximum walk-sum tree; subgraph preconditioners; walk-sum diagrams; walk-sums
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number9921322
Issue or Number:5
Record Number:CaltechAUTHORS:20121005-083046659
Persistent URL:
Official Citation:Chandrasekaran, V.; Johnson, J.K.; Willsky, A.S.; , "Estimation in Gaussian Graphical Models Using Tractable Subgraphs: A Walk-Sum Analysis," Signal Processing, IEEE Transactions on , vol.56, no.5, pp.1916-1930, May 2008 doi: 10.1109/TSP.2007.912280 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34694
Deposited By: Tony Diaz
Deposited On:08 Oct 2012 21:30
Last Modified:09 Nov 2021 23:10

Repository Staff Only: item control page