Multiscale stochastic modeling for tractable inference and data assimilation

We consider a class of multiscale Gaussian models on pyramidally structured graphs. While such models have been considered in the past, very recent advances in inference methods for graphical models not only yield additional motivation for this class of models but also bring techniques that lead to new and powerful algorithms. We provide a brief summary of these recent advances – including so-called walk-sum analysis, methods based on Lagrangian relaxation, and a new method for “low-rank,” wavelet-based, unbiased estimation of error variances – and then adapt and apply them to problems of estimation for pyramidal models. We demonstrate that our models not only capture long-range dependencies but that they also have the property that conditioned on neighboring scales, the correlation behavior within a scale is dramatically compressed. This leads to algorithms resembling multipole methods for solving partial differential equations in which we alternate computations across-scale (using an embedded tree in the pyramidal graph) with local updates within each scale. Not only are these algorithms guaranteed to converge to the correct answers but they also lead to new, adaptive methods for choosing embedded trees and subgraphs to achieve rapid convergence. This approach also leads to a solution to the so-called re-estimation problem in which we seek to update an estimate rapidly after local changes are made to the prior model or to the available data. In addition, by using a consistent probabilistic model across as well as within scales, we are able both to exploit low-rank variance estimation methods and to develop efficient iterative algorithms for parameter estimation.