Stochastic Systems Group  

Lowrank variance approximation in largescale GMRF models
Dmitry Malioutov
SSG, MIT
We consider the problem of variance approximation in largescale GaussMarkov 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 rankreduced 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 multiscale extension for models with longrange 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 jonesb@mit.edu