Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Tree-Based Modeling and Estimation
of Gaussian Processes on Graphs with Cycles

Erik Sudderth
SSG Master's student

Stochastic processes defined on graphs arise in a variety of fields, including coding theory, statistical image processing, and remote sensing. If the graph is tree-structured (contains no loops), there exist direct and efficient algorithms for statistical inference. Unfortunately, many stochastic processes are not well approximated by a tree-structured graph, motivating the development of efficient techniques for modeling and inference using graphs with cycles.

I will discuss the embedded trees algorithm, an iterative technique for estimation of Gaussian processes defined on arbitrary graphs. By exploiting a sequence of embedded spanning trees, it computes the conditional means with an efficiency comparable to or better than other techniques. Unlike other methods, the embedded trees algorithm also computes exact error covariances. The algorithm is especially efficient in application to "near-trees", in which removing a small number of edges reveals an embedded tree. In this context, I will demonstrate that near-tree graphs have the potential to provide a significant increase in modeling power, with only a minor increase in estimation complexity. Preliminary insights into the geometric structure of the algorithm will also be discussed.

Problems with this site should be emailed to