Sparse Cholesky factorization by Kullback-Leibler minimization

DOI10.1137/20M1336254MaRDI QIDQ6339715arXivFDO

Authors Florian Schäfer, Matthias Katzfuss, Houman Owhadi

Publication date 29 April 2020

Published in arXiv

Full work available at URL https://doi.org/10.1137/20M1336254

Mathematics Subject Classification ID

Nontrigonometric harmonic analysis involving wavelets and other special systems (42C40) Martingales with discrete parameter (60G42) Computational methods for sparse matrices (65F50) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs (65N75) Analysis of algorithms (68W40)

arXiv classification

cs.NAmath.NAmath.OCmath.STstat.COstat.TH

Abstract: 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 $mathcalN(0,Theta)$ and $mathcalN(0,L^{-op}{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 ${x_i}_{1leqileqN}subsetmathbb{R}^d$, we propose an elimination ordering and sparsity pattern that allows us to compute $epsilon$-approximate inverse Cholesky factors of such $Theta$ in computational complexity $mathcalO(Nlog(N/epsilon{)}^d)$ in space and $mathcalO(Nlog(N/epsilon{)}^{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.

Cited in

(3)

• A recursive butterfly factorization with optimality guarantees
• Linear-cost Polyharmonic Spline Interpolation of Arbitrary Degree
• Optimal Recovery for Solving Variational Problems

This page was built for publication: Sparse Cholesky factorization by Kullback-Leibler minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6339715)