Butterfly-Accelerated Gaussian Random Fields on Manifolds
Paul Beckman, New York University
Gaussian random fields are a class of stochastic process models which are widely used in spatial statistics and Bayesian inverse problems. However, the covariance matrix that defines the distribution of any finite set of observations is generally dense, which poses a computational challenge for large sample sizes. For stationary covariance functions in the plane, there exist several methods which express the random field as a superposition of Fourier modes, and use the fast Fourier transform (FFT) to accelerate computations. We propose a generalization of these methods for Gaussian random fields on manifolds. We express the random field in terms of eigenfunctions of the Laplace-Beltrami operator, and use a butterfly factorization - an algebraic generalization of the FFT - to accelerate computations. We demonstrate the performance of our method on triangle meshes discretized with finite elements, and discuss its application as a prior in Bayesian inverse scattering problems.