# Novel Pivoted Cholesky Decompositions for Efficient Gaussian Process Inference

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 28 Jul 2025.

## Builds on (most cited first, 16 of 16)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Understanding Probabilistic Sparse Gaussian Process Approximations](https://mlsanity.com/paper/1606.04820/) (2016)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity](https://mlsanity.com/paper/1706.02205/) (2017)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [High-Dimensional Gaussian Process Inference with Derivatives](https://mlsanity.com/paper/2102.07542/) (2021)
- [Safe Active Learning for Time-Series Modeling with Gaussian Processes](https://mlsanity.com/paper/2402.06276/) (2024)
- [Memory-Based Dual Gaussian Processes for Sequential Learning](https://mlsanity.com/paper/2306.03566/) (2023)
- [Near-Optimal Active Learning of Multi-Output Gaussian Processes](https://mlsanity.com/paper/1511.06891/) (2015)
- [Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation](https://mlsanity.com/paper/2206.08366/) (2022)
- [Sparse Bayesian Learning via Stepwise Regression](https://mlsanity.com/paper/2106.06095/) (2021)
- [Exact Sampling from Determinantal Point Processes](https://mlsanity.com/paper/1609.06840/) (2016)

## Abstract (arXiv)

The Cholesky decomposition is a fundamental tool for solving linear systems with symmetric and positive definite matrices which are ubiquitous in linear algebra, optimization, and machine learning. Its numerical stability can be improved by introducing a pivoting strategy that iteratively permutes the rows and columns of the matrix. The order of pivoting indices determines how accurately the intermediate decomposition can reconstruct the original matrix, thus is decisive for the algorithm's efficiency in the case of early termination. Standard implementations select the next pivot from the largest value on the diagonal. In the case of Bayesian nonparametric inference, this strategy corresponds to greedy entropy maximization, which is often used in active learning and design of experiments. We explore this connection in detail and deduce novel pivoting strategies for the Cholesky decomposition. The resulting algorithms are more efficient at reducing the uncertainty over a data set, can be updated to include information about observations, and additionally benefit from a tailored implementation. We benchmark the effectiveness of the new selection strategies on two tasks important to Gaussian processes: sparse regression and inference based on preconditioned iterative solvers. Our results show that the proposed selection strategies are either on par or, in most cases, outperform traditional baselines while requiring a negligible amount of additional computation.