MURI Research
Topic: Modeling and Estimation of Gaussian Processes on Graphs with Cycles
By: Erik Sudderth (MIT), Martin Wainwright (MIT), Alan S. Willsky (MIT)
Statistical models of two-dimensional fields play an important role in a variety of application areas, from oceanography to image processing. Markov random fields, perhaps the most common means of representing a two-dimensional random process, have an intuitively appealing structure, but they generally lead to computationally intensive estimation algorithms. The multiscale tree models previously introduced by the Stochastic Systems Group provide highly efficient estimation procedures. The fundamental source of the efficiency of tree-based algorithms is that there is a single unique path between any two points in the tree - in other words, there are no loops. Unfortunately, the tree structure also tends to lead to blocky artifacts in the final estimation results. This research involves the investigation of model structures that lie in between densely connected Markov random fields and singly connected multiscale trees. We have developed a novel estimation algorithm which computes the exact means and error covariances for Gaussian estimation problems on arbitrary cyclic graphs. It works by exploiting the presence of tree-like structures in more densely connected graphs. Current work focuses on obtaining a deeper understanding of this algorithm\'s dynamics, and on determining efficient procedures for constructing models on graphs with cycles.

Questions and comments to the webmaster. This page is copyrighted by the Massachusetts Institute of Technology.