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

We present the embedded trees algorithm, an iterative technique for estimation of Gaussian processes defined on arbitrary graphs. By exactly solving a series of modified problems on embedded spanning trees,it computes the conditional means with an efficiency comparable to or better than other techniques. Theerror covariance computation is most efficient for graphs in which removing a small number of edges reveals an embedded tree.In this context, we demonstrate that sparse loopy graphs can provide a significant increase in modeling power relative totrees, with only a minor increase in estimation complexity. 1 Introduction Graphical models are an invaluable tool for defining and manipulating probability distributions. In modeling stochastic processes with graphical models, two basic problems arise: (i) specifying a class of graphs with which to model or approximate the process; and (ii) determining efficient techniques for statistical inference. At one extreme are tree-structured graphs: although they lead to highly efficient algorithms for estimation [1, 2], their modeling power is often limited.