Permutation Methods for Sharpening Gaussian Process Approximations

Abstract

Vecchia's approximate likelihood for Gaussian process parameters depends on how the observations are ordered, which can be viewed as a deficiency because the exact likelihood is permutation-invariant. This article takes the alternative standpoint that the ordering of the observations is an aspect that can be tuned to sharpen the approximations. Advantageously chosen orderings of the observations can drastically improve the approximations, and in fact, completely random orderings often produce far more accurate approximations than default coordinate-based orderings do. In addition to the permutation results, automatic methods for grouping calculations of components of the approximation are introduced, having the result of simultaneously improving the quality of the approximation and reducing its computational burden. In one common setting, reordering combined with grouping reduces the Kullback-Leibler divergence from the target model by a factor of 80 and the computation time by a factor of 2 compared to ungrouped approximations with a default ordering. The claims are supported by theory and numerical results, and details of implementation are provided, including how to efficiently find the orderings and ordered nearest neighbors, and how to use the approximations for prediction and conditional simulation. An application to uncertainty quantification in interpolations of space-time satellite data is presented.