Kriging in low-rank tensor format

Overview

Details

​Computational power poses heavy limitations to the achievable problem size for Kriging. In separate research lines, Kriging algorithms based on FFT, the separability of certain covariance functions and low-rank representations of covariance functions have been investigated, all three leading to drastic speedup factors. The current study combines these ideas, and so combines the individual speedup factors of all ideas. This way, we reduce the mathematics behind Kriging to the log-linear computational complexity. For separable factorized covariance functions, the results are exact, and non-separable covariance functions can be approximated well through sums of separable components.

In illustrative numerical test cases, we achieve speedup factors up to 108  -eight orders of magnitude-, and we can treat problem sizes of up to 15 trillion and two quadrillion estimation points for Kriging and spatial design, respectively, within seconds on a contemporary desktop computer.

The current study assumes second-order stationarity and simple Kriging on a regular, equispaced lattice, without working with restricted neighborhoods.
Extensions to many other cases are straightforward.

An example shows the concentration of an ore mineral. Domain: 20m × 20m × 20m, n = 250003 points, m = 4000  measurements randomly distributed within the volume, with increasing data density towards the lower left back corner of the domain. The covariance model is anisotropic Gaussian with unit variance and with 32 correlation lengths fitting into the domain in the horizontal directions, and 64 correlation lengths fitting into the vertical direction. The top left figure shows the entire domain at a sampling rate of 1:64 per direction, and then a series of zooms into the respective lower left back corner with zoom factors sampling rates of 4 1:16, 16 1:4, 64 1:1 for the top right, bottom left and bottom right plots, respectively. Color scale: showing the 95% confidence interval [μ － 2σ, μ + 2σ].

Publications

• ​​Nowak, W., Litvinenko, A. Kriging and Spatial Desi​gn Accelerated by Orders of Magnitude: Combining Low-Rank Covariance Approximations with FFT-Techniques​, Mathematical Geosciences, Vol. 45, Num. 4, pp 411--435, Springer 2013.