Gaussian processes are a cornerstone of probabilistic machine learning, yet scaling them to large datasets usually forces a trade‑off between computational efficiency and model fidelity. This paper introduces an adaptive multi‑resolution Gaussian process framework that remains exact while being scalable. The key innovation is a naturally data‑sparse covariance matrix built from adaptive multi‑resolution basis functions anchored directly to the training samples, eliminating the need for auxiliary points. By shrinking the support domains of these bases, the sizes of matrix blocks are bounded, guaranteeing sparsity. The inverse of the sparse covariance matrix is computed exactly and efficiently via a sparse Cholesky inverse algorithm. To further improve predictive uncertainties, an augmented basis function is added. Theoretical analysis shows a training cost of $O(n \log^2 n)$ and a prediction cost of $O(\log^d n)$, and numerical experiments confirm that the model achieves high‑fidelity inference with fast computation.
Review