Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 3, 2021 | Published + Submitted
Journal Article Open

Sparse Cholesky Factorization by Kullback-Leibler Minimization


We propose to compute a sparse approximate inverse Cholesky factor L of a dense covariance matrix Θ by minimizing the Kullback--Leibler divergence between the Gaussian distributions N(0,Θ) and N(0,L^(−⊤)L⁻¹), 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 Θ obtained from pairwise evaluation of Green's functions of elliptic boundary-value problems at points {x_i}_(1≤i≤N) ⊂ ℝ^d, we propose an elimination ordering and sparsity pattern that allows us to compute ϵ-approximate inverse Cholesky factors of such Θ 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 its optimality properties, we propose applying our method 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, compromising neither accuracy nor computational complexity.

Additional Information

© 2021, Society for Industrial and Applied Mathematics. Submitted to the journal's Methods and Algorithms for Scientific Computing section May 6, 2020; accepted for publication (in revised form) January 27, 2021; published electronically June 3, 2021. Funding: The work of the first and third authors was supported by the Air Force Office of Scientific Research under award FA9550-18-1-0271 (Games for Computation and Learning) and by the Office of Naval Research under award N00014-18-1-2363. The work of the second author was partially supported by National Science Foundation (NSF) through grants DMS-1654083, DMS-1953005, and CCF-1934904. We thank the two anonymous referees for their constructive feedback, which helped us to improve the article.

Attached Files

Published - 20m1336254.pdf

Submitted - 2004.14455.pdf


Files (19.8 MB)
Name Size Download all
9.0 MB Preview Download
10.9 MB Preview Download

Additional details

August 20, 2023
October 20, 2023