Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Matérn Correlations
This solves the computational bottleneck for Gaussian process regression in one-dimensional and grid-based multi-dimensional settings, offering a practical improvement for applications in statistics and machine learning.
The authors developed an exact and scalable algorithm for Gaussian process regression with Matérn correlations, achieving linear computational cost of O(ν^3 n) operations and O(νn) storage, which significantly outperforms existing methods in speed and accuracy.
We develop an exact and scalable algorithm for one-dimensional Gaussian process regression with Matérn correlations whose smoothness parameter $ν$ is a half-integer. The proposed algorithm only requires $\mathcal{O}(ν^3 n)$ operations and $\mathcal{O}(νn)$ storage. This leads to a linear-cost solver since $ν$ is chosen to be fixed and usually very small in most applications. The proposed method can be applied to multi-dimensional problems if a full grid or a sparse grid design is used. The proposed method is based on a novel theory for Matérn correlation functions. We find that a suitable rearrangement of these correlation functions can produce a compactly supported function, called a "kernel packet". Using a set of kernel packets as basis functions leads to a sparse representation of the covariance matrix that results in the proposed algorithm. Simulation studies show that the proposed algorithm, when applicable, is significantly superior to the existing alternatives in both the computational time and predictive accuracy.