Team for Research in
Ubiquitous Secure Technology

Citation
Venkat Chandrasekaran, Jason K. Johnson, Alan S. Willsky. "Estimation in Gaussian Graphical Models using Tractable Subgrahs: A Walk-Sum Analysis". IEEE Transactions on Signal Processing (accepted), July 2007.

Abstract
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 “computed” 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 non-stationary algorithms provide a significant speedup in convergence over traditional one-tree and two-tree iterations.

Electronic downloads

• cjw_walksum_tsp07.pdf · application/pdf · 413 kbytes

• HTML

  Venkat Chandrasekaran, Jason K. Johnson, Alan S. Willsky.
  <a href="http://www.truststc.org/pubs/267.html"
  >Estimation in Gaussian Graphical Models using Tractable
  Subgrahs: A Walk-Sum Analysis</a>, <i>IEEE
  Transactions on Signal Processing (accepted)</i>, July
  2007.

• Plain text

  Venkat Chandrasekaran, Jason K. Johnson, Alan S. Willsky.
  "Estimation in Gaussian Graphical Models using
  Tractable Subgrahs: A Walk-Sum Analysis". <i>IEEE
  Transactions on Signal Processing (accepted)</i>, July
  2007.

• BibTeX

  @article{ChandrasekaranJohnsonWillsky07_EstimationInGaussianGraphicalModelsUsingTractableSubgrahs,
      author = {Venkat Chandrasekaran and Jason K. Johnson and
                Alan S. Willsky},
      title = {Estimation in Gaussian Graphical Models using
                Tractable Subgrahs: A Walk-Sum Analysis},
      journal = {IEEE Transactions on Signal Processing (accepted)},
      month = {July},
      year = {2007},
      abstract = {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 �computed� 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 non-stationary algorithms
                provide a significant speedup in convergence over
                traditional one-tree and two-tree iterations.},
      URL = {http://www.truststc.org/pubs/267.html}
  }
  

Posted by Venkat Chandrasekaran on 21 Jul 2007.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.