GMRF Variance Approximation using Splicedwavelet Bases

We consider the problem of computing variances in large-scale Gauss-Markov random field (GMRF) models. In our prior work we considered the short-range correlation case, and we proposed a simple low-rank method which computes approximate variances with linear complexity in the number of nodes. In addition to its low complexity, the method has good guarantees on the quality of the approximation. In this paper we extend our method and analysis using a wavelet-based multi-scale approach which is applicable to models with much longer correlation lengths.