Efficient kriging for real-time spatio-temporal interpolation

In many fields within atmospheric science and meteorology, data is often recorded at scattered station locations. These data are generally available over a long period of time. However, in order to utilize the data for efficient analysis, the data cannot be used directly, and would need to be interpolated both spatially and temporally. This is necessary both to organize the station recording to a regular grid and to possibly query for values at a particular location or time of interest.

Spatio-temporal interpolation approaches require the evaluation of weights at each point of interest. A popular and widely used interpolation approach is kriging. Kriging has the advantage that it provides an unbiased estimate with least error variance. However, kriging based weight evaluation have a cubic time complexity for each point of interest, thus resulting in a time complexity of O(N⁴) for interpolation at O(N) points

In this work, we formulate the kriging problem, to, first, reduce the computational complexity to O(N³). Further, we use the fast summation algorithm, FIGTREE [1] along with an iterative approach SymmLQ to reduce the complexity to O(N). We illustrate the speedup on synthetic data for both spatial and spatio-temporal kriging. We compare the performance with another fast approach [2] and standard software. We then apply the developed fast approach to real data.

References

[1]. V. I. Morariu, B. V. Srinivasan, V. C. Raykar, R. Duraiswami, and L. Davis. "Automatic online tuning for fast Gaussian summation". In NIPS. MIT Press, 2008

[2]. S. Sakata, F. Ashidaa and M. Zakob, "An efficient algorithm for Kriging approximation and optimization with large-scale sampling data", Computer Methods in Applied Mechanics and Engineering, Volume 193, Number 3, 23 January 2004 , pp. 385-404(20)