  With the advent of massive data sets much of the computational science and
engineering community has moved toward data-intensive approaches in regression
and classification. However, these present significant challenges due to
increasing size, complexity and dimensionality of the problems. In particular,
covariance matrices in many cases are numerically unstable and linear algebra
shows that often such matrices cannot be inverted accurately on a finite
precision computer. A common ad hoc approach to stabilizing a matrix is
application of a so-called nugget. However, this can change the model and
introduce error to the original solution. It is well known from numerical
analysis that ill-conditioned matrices cannot be accurately inverted. In this
paper we develop a multilevel computational method that scales well with the
number of observations and dimensions. A multilevel basis is constructed
adapted to a kD-tree partitioning of the observations. Numerically unstable
covariance matrices with large condition numbers can be transformed into well
conditioned multilevel ones without compromising accuracy. Moreover, it is
shown that the multilevel prediction exactly solves the Best Linear Unbiased
Predictor (BLUP) and Generalized Least Squares (GLS) model, but is numerically
stable. The multilevel method is tested on numerically unstable problems of up
to 25 dimensions. Numerical results show speedups of up to 42,050 times for
solving the BLUP problem, but with the same accuracy as the traditional
iterative approach. For very ill-conditioned cases the speedup is infinite. In
addition, decay estimates of the multilevel covariance matrices are derived
based on high dimensional interpolation techniques from the field of numerical
analysis. This work lies at the intersection of statistics, uncertainty
quantification, high performance computing and computational applied
mathematics.
