Adaptive Nyström for Gaussian Process Regression

Gaussian Process Regression (GPR) is a robust framework for uncertainty quantification, yet its O(n^3) complexity limits its scalability. Low-rank Nyström approximations can reduce this burden to O(nm^2), but their accuracy depends heavily on the selection of landmark points. We propose an adaptive Nyström approach that greedily selects landmarks to minimize the trace residual of the kernel approximation error. Unlike static approximations, our method interleaves landmark expansion with hyperparameter optimization, allowing the selection process to adapt as the covariance structure is refined. Numerical experiments on five benchmark functions demonstrate that this method significantly outperforms random landmark selection in both accuracy and stability. It achieves predictive performance comparable to exact GP inference while maintaining linear scaling with respect to the sample size, providing a principled and efficient framework for large-scale computer experiments.