# Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning

arXiv: https://arxiv.org/abs/1905.10587 · HTML: https://mlsanity.com/paper/1905.10587/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2019.

## Built on by (most cited first, 6 of 6)

- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Practical multi-fidelity machine learning: fusion of deterministic and Bayesian models](https://mlsanity.com/paper/2407.15110/) (2024)
- [Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence](https://mlsanity.com/paper/2212.12737/) (2022)
- [Provably Reliable Large-Scale Sampling from Gaussian Processes](https://mlsanity.com/paper/2211.08036/) (2022)
- [Accelerating Regularized Attention Kernel Regression for Spectrum Cartography](https://mlsanity.com/paper/2604.25138/) (2026)
- [The Geometry of the Pivot: A Note on Lazy Pivoted Cholesky and Farthest Point Sampling](https://mlsanity.com/paper/2601.03706/) (2026)

## Abstract (arXiv)

This paper presents a method for building a preconditioner for a kernel ridge regression problem, where the preconditioner is not only effective in its ability to reduce the condition number substantially, but also efficient in its application in terms of computational cost and memory consumption. The suggested approach is based on randomized matrix decomposition methods, combined with the fast multipole method to achieve an algorithm that can process large datasets in complexity linear to the number of data points. In addition, a detailed theoretical analysis is provided, including an upper bound to the condition number. Finally, for Gaussian kernels, the analysis shows that the required rank for a desired condition number can be determined directly from the dataset itself without performing any analysis on the kernel matrix.