Gaussian processes constitute a cornerstone of probabilistic machine learning, yet scaling them to large datasets typically forces a trade-off between computational efficiency and model fidelity. This work bridges this gap by presenting an adaptive multi-resolution Gaussian process framework that is both scalable and exact. Our key innovation is constructing a naturally data-sparse covariance matrix with adaptive multi-resolution basis functions. These basis functions are directly anchored to samples, eliminating the need for auxiliary points. By shrinking the support domains of multi-resolution basis, the matrix block sizes are limited, guaranteeing sparsity. The inverse of the data-sparse covariance matrix is computed exactly and efficiently via the sparse Cholesky inverse algorithm. To further improve predictive uncertainties, we construct an augmented basis function. Theoretical analysis and numerical experiments demonstrate that our model achieves exact inference with O(nlog2n) training cost and O(logdn) prediction cost, establishing a principled framework for scalable and high-fidelity Gaussian process regression.
Figures & tables
Figure 1: Examples of our adaptive multi-resolution basis for samples with ρ=2.5 in [0,10] .
Figure 2: For this tree structure, the nodes are collected in nested dissection order as {4,5,2,8,9,6,7,3,1} .
Figure 3: Sparse pattern of matrices in an AMRGP model with 10,000 samples.
Table 1: Synthetic data used in numerical experiments.
Figure 4: Synthetic data.
Figure 5: OpenMP parallel computing with 1 million data points.
Figure 6: Performance of our AMRGP on Case 7 with different ρ ’s and m ’s.
Figure 7: Performance of our AMRGP on Case 8 with different ρ ’s and m ’s.
Case
1
2
3
4
5
6
Time (s)
25.9
20.5
19.9
23.4
20.6
20.2
Memory (GB)
11.5
11.5
11.5
11.5
11.5
11.5
Normalized CRPS
0.004
0.002
0.345
0.009
0.013
0.024
Table 2: Performance of the choice ρ=4.0 and m=100 on Case 1–6 with 1 million training data points.
Figure 8: Complexity of our AMRGP.
Case
Dimension
Metric
SVGP
SKIP
SVecGP
AMRGP
1
1
Time cost (s)
123.4 (2.5)
77.7 (1.5)
58.8 (7.1)
5.1 (3.8)
Normalized CRPS × 100
0.12
0.02
0.01
0.10
2
1
Time cost (s)
125.3 (2.5)
86.1 (1.5)
57.4 (6.9)
3.3 (1.6)
Normalized CRPS × 100
2.11
2.73
0.07
0.21
3
2
Time cost (s)
131.7 (2.6)
176.0 (3.4)
84.0 (8.9)
2.8 (2.3)
Normalized CRPS × 100
0.22
0.59
1.15
0.99
Table 3: Comparison of scalable GP models. The time in parenthesis is the average time cost by one iteration in approximate GPs and the training time in AMRGP.
Figure 9: Predictions for Case 2.
Figure 10: Predictions for Case 4: exact and predicted values (top) and standard deviations (bottom).
Figure 11: Prediction for the Burger’s equation over the computational domain.
Figure 12: Predicted for the wave equation over the computational domain. The black rectangle denotes the test region.