A Caltech Library Service

Sparse Cholesky factorization by Kullback-Leibler minimization

Schäfer, Florian and Katzfuss, Matthias and Owhadi, Houman (2020) Sparse Cholesky factorization by Kullback-Leibler minimization. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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−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 Θ 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(Nlog(N/ϵ)^d) in space and O(Nlog(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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Owhadi, Houman0000-0002-5677-1600
Additional Information:FS and HO gratefully acknowledge support by the Air Force Office of Scientific Research under award number FA9550-18-1-0271 (Games for Computation and Learning), and the Office of Naval Research under award N00014-18-1-2363 (Toward scalable universal solvers for linear systems). MK's research was partially supported by National Science Foundation (NSF) grants DMS-1654083, DMS-1953005, and CCF-1934904. The computations in subsection 5.4 were conducted on the Caltech High-Performance Cluster partially supported by a grant from the Gordon and Betty Moore Foundation.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0271
Office of Naval Research (ONR)N00014-18-1-2363
Gordon and Betty Moore FoundationUNSPECIFIED
Subject Keywords:Covariance function, Vecchia approximation, kernel matrix, sparsity, transport map, factorized sparse approximate inverse
Classification Code:AMS subject classifications. 65F30 (42C40, 65F50, 65N55, 65N75, 60G42, 68W40)
Record Number:CaltechAUTHORS:20201109-155534680
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106572
Deposited By: George Porter
Deposited On:10 Nov 2020 15:25
Last Modified:10 Nov 2020 15:25

Repository Staff Only: item control page