# Sparse Cholesky factorization by Kullback-Leibler minimization

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2020.

## Built on by (most cited first, 30 of 41)

- [Solving and Learning Nonlinear PDEs with Gaussian Processes](https://mlsanity.com/paper/2103.12959/) (2021)
- [Kernel Methods are Competitive for Operator Learning](https://mlsanity.com/paper/2304.13202/) (2023)
- [Sparse Cholesky Factorization for Solving Nonlinear PDEs via Gaussian Processes](https://mlsanity.com/paper/2304.01294/) (2023)
- [Computational Graph Completion](https://mlsanity.com/paper/2110.10323/) (2021)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Error Analysis of Kernel/GP Methods for Nonlinear and Parametric PDEs](https://mlsanity.com/paper/2305.04962/) (2023)
- [Scalable Bayesian Optimization Using Vecchia Approximations of Gaussian Processes](https://mlsanity.com/paper/2203.01459/) (2022)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Scalable Gaussian-process regression and variable selection using Vecchia approximations](https://mlsanity.com/paper/2202.12981/) (2022)
- [Toward Efficient Kernel-Based Solvers for Nonlinear PDEs](https://mlsanity.com/paper/2410.11165/) (2024)
- [Data-Efficient Kernel Methods for Learning Differential Equations and Their Solution Operators: Algorithms and Error Analysis](https://mlsanity.com/paper/2503.01036/) (2025)
- [Operator Learning at Machine Precision](https://mlsanity.com/paper/2511.19980/) (2025)
- [Iterative Methods for Vecchia-Laplace Approximations for Latent Gaussian Process Models](https://mlsanity.com/paper/2310.12000/) (2023)
- [Gaussian Process Hydrodynamics](https://mlsanity.com/paper/2209.10707/) (2022)
- [Variational sparse inverse Cholesky approximation for latent Gaussian processes via double Kullback-Leibler minimization](https://mlsanity.com/paper/2301.13303/) (2023)
- [Gaussian Measures Conditioned on Nonlinear Observations: Consistency, MAP Estimators, and Simulation](https://mlsanity.com/paper/2405.13149/) (2024)
- [Iterative Methods for Full-Scale Gaussian Process Approximations for Large Spatial Data](https://mlsanity.com/paper/2405.14492/) (2024)
- [A friendly introduction to triangular transport](https://mlsanity.com/paper/2503.21673/) (2025)
- [Learning particle swarming models from data with Gaussian processes](https://mlsanity.com/paper/2106.02735/) (2021)
- [Learning solution operator of dynamical systems with diffusion maps kernel ridge regression](https://mlsanity.com/paper/2512.17203/) (2025)
- [Conjugate gradient methods for high-dimensional GLMMs](https://mlsanity.com/paper/2411.04729/) (2024)
- [Neural Triangular Transport Maps: A New Approach Towards Sampling in Lattice QCD](https://mlsanity.com/paper/2510.13112/) (2025)
- [Fast Gaussian Process Approximations for Autocorrelated Data](https://mlsanity.com/paper/2512.02925/) (2025)
- [Variational Bayesian inference for CP tensor completion with side information](https://mlsanity.com/paper/2206.12486/) (2022)
- [Adaptive LASSO estimation for functional hidden dynamic geostatistical model](https://mlsanity.com/paper/2208.05528/) (2022)
- [Scalable Model-Based Gaussian Process Clustering](https://mlsanity.com/paper/2309.07882/) (2023)
- [Implementation and Analysis of GPU Algorithms for Vecchia Approximation](https://mlsanity.com/paper/2407.02740/) (2024)
- [Learning non-Gaussian spatial distributions via Bayesian transport maps with parametric shrinkage](https://mlsanity.com/paper/2409.19208/) (2024)
- [BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions](https://mlsanity.com/paper/2505.12289/) (2025)
- [Tensor Gaussian Processes: Efficient Solvers for Nonlinear PDEs](https://mlsanity.com/paper/2510.13772/) (2025)

## Abstract (arXiv)

We propose to compute a sparse approximate inverse Cholesky factor L of a dense covariance matrix Theta by minimizing the Kullback-Leibler divergence between the Gaussian distributions N(0, Theta) and N(0, L-top L-1), subject to a sparsity constraint. Surprisingly, this problem has a closed-form solution that can be computed efficiently, recovering the popular Vecchia approximation in spatial statistics. Based on recent results on the approximate sparsity of inverse Cholesky factors of Theta obtained from pairwise evaluation of Green's functions of elliptic boundary-value problems at points xi1 ≤ i ≤ N subset ℝd, we propose an elimination ordering and sparsity pattern that allows us to compute ε-approximate inverse Cholesky factors of such Theta in computational complexity O(N log(N/ε)d) in space and O(N log(N/ε)2d) in time. To the best of our knowledge, this is the best asymptotic complexity for this class of problems. Furthermore, our method is embarrassingly parallel, automatically exploits low-dimensional structure in the data, and can perform Gaussian-process regression in linear (in N) space complexity. Motivated by the optimality properties of our methods, we propose methods for applying it to the joint covariance of training and prediction points in Gaussian-process regression, greatly improving stability and computational cost. Finally, we show how to apply our method to the important setting of Gaussian processes with additive noise, sacrificing neither accuracy nor computational complexity.