Title: Accelerating Metroplis-within-Gibbs sampler with localized computations of differential equations
Authors: Qiang Liu - National University of Singapore (Singapore) [presenting]
Xin Tong - National University of Singapore (Singapore)
Abstract: Bayesian inverse problem is widely encountered when quantifying uncertainty for underlying parameters in practice. For high dimensional spatial models, classical Markov chain Monte Carlo (MCMC) methods are ususlly slow to be applied, while it has been shown that Metropolis-within-Gibbs (MwG) sampling works when the parameters are locally dependent. The problem is that its implementation requires $O(n^2)$ calculation, where $n$ is the number of parameters. Our target in this paper is to reduce the computation cost to an optimal scalability of $O(n)$, in the framework of stochastic differential equation (SDE) with local dependence structure. The key is that MwG proposal is only different from the original at local entries, and the difference caused also evolves locally. This inspires us to approximate the solution for the proposal with a surrogate updated only within a local domain, which brings down the computation to our targeting level. Both theoretically and numerically, we prove that the induced errors can be controlled by the local domain size. Implementions of our computation scheme by using Euler-Maruyama and 4th order Runge-Kutta method are also discussed. We demonstrate the finite sample performance of our method in numerical examples of Lorenz 96 and a linear stochastic flow model.