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

SSG Seminar Abstract

Low-rank variance approximation in large-scale GMRF models

Dmitry Malioutov

We consider the problem of variance approximation in large-scale Gauss-Markov random field (GMRF) models. While approximate mean estimates can be obtained efficiently for sparse GMRFs of very large size, computing the variances is a challenging problem. We propose a simple rank-reduced method which exploits the graph structure and the correlation length in the model to compute approximate variances with linear complexity in the number of nodes. The method has a separation length parameter trading off complexity versus estimation accuracy. For models with bounded correlation length, we efficiently compute provably accurate variance estimates.

We also propose a multi-scale extension for models with long-range dependence. We use wavelets to decompose the correlation into several frequency bands, thus reducing the problem with long correlation length to a group of problems with short correlation length.

Joint work with Jason Johnson.

Problems with this site should be emailed to