Efficient kriging for real-time spatio-temporal interpolation
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(N4) for interpolation at O(N) points
In this work, we formulate the kriging problem, to, first, reduce the computational complexity to O(N3). Further, we use the fast summation algorithm, FIGTREE  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  and standard software. We then apply the developed fast approach to real data.
. 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
. 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)