Convergence of pivoted Cholesky for Lipschitz kernels

Abstract

We investigate the continuous analogue of the Cholesky factorization, namely the pivoted Cholesky algorithm. Our analysis establishes quantitative convergence guarantees for kernels of minimal smoothness. We prove that for a symmetric positive definite Lipschitz continuous kernel $K:\Omega \times \Omega \to \mathbb{R}$ on a compact domain $\Omega \subset {\mathbb{R}}^d$, the residual of the Cholesky algorithm with complete pivoting (where the maximum value of the diagonal of the residual is selected as the next pivot) is uniformly bounded above by a constant multiple of the separation distance of the pivots, which implies the convergence rate $\Vert R_n{\Vert }_{\infty }=\mathcal{O}(n^{-1/d})$, where $R_n$ is the residual after $n$ Cholesky steps and $\Vert \cdot {\Vert }_{\infty }$ is the supremum norm. Along the way, we show that for any pivoting strategy, $\Vert R_n{\Vert }_{\infty }$ is bounded by a constant multiple of the fill distance of the pivots. Moreover, if $K$ is differentiable in both variables with a Lipschitz derivative and $\Omega$ is convex, our convergence rate improves to $\mathcal{O}(n^{-2/d})$. Our result closes a gap between theory and practice as previous analyses required $K$ to be $C^2$-regular or translation invariant to establish convergence, whereas empirical evidence indicated robust performance even for non-differentiable kernels. We further prove a connection between the Cholesky algorithm and the P-greedy interpolation method, as well as downstream applications to Gaussian process regression and matrix Cholesky factorization.

arXiv comment19 pages, 4 figures