High dimensional multilevel Kriging: A computational mathematics approach

With the advent of massive data sets much of the computational science and engineering communities have been moving toward data-driven approaches such as regression and classification. However, they present a significant challenge due to the increasing size, complexity and dimensionality of the problems. In this paper a multilevel Kriging method that scales well with the number of observations and dimensions is developed. A multilevel basis is constructed that is adapted to a kD-tree partitioning of the observations. Numerically unstable covariance matrices with large condition numbers are transformed into well conditioned multilevel matrices without compromising accuracy. Moreover, it is shown that the multilevel prediction $exactly$ solves the Best Linear Unbiased Predictor (BLUP), but is numerically stable. The multilevel method is tested on numerically unstable problems of up 25 dimensions. Numerical results show speedups of up to 42,050 for solving the BLUP problem but to the same accuracy than the traditional iterative approach.