Walk-Sum Analysis in Gaussian MRFs

Jason K. Johnson, Dmitry M. Malioutov, Venkat Chandrasekaran

An interesting spin-off of Jason's work in GMRFs has been the novel walk-sum interpretation of inference in Gaussian graphical models. In a technical report, Jason introduced the class of walk-summable models; characterized some important, easily identified sub-classes of these models and provided a walk-sum analysis of certain iterative estimation algorithms, namely, the Gauss-Jacobi iteration, the (stationary) embedded-tree (ET) algorithm and a special-case of the cyclic, two-tree ET iteration. Later on, in joint work with Dmitry Malioutov, this picture was further refined and applied to give a new interpretation of Gaussian belief propagation, which was therefore shown to converge in walk-summable models. Later still, Venkat and Jason generalized the walk-sum interpretation of ET to a much broader class of algorithms, including iterations based on arbitrary (non-cyclic) sequences of tractable sub-graphs.