Stochastic Systems Group  

Stochastic processes defined on graphs arise in a variety of fields, including coding theory, statistical image processing, and remote sensing. If the graph is treestructured (contains no loops), there exist direct and efficient algorithms for statistical inference. Unfortunately, many stochastic processes are not well approximated by a treestructured 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 "neartrees", in which removing a small number of edges reveals an embedded tree. In this context, I will demonstrate that neartree 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 jonesb@mit.edu