Estimating Kernel-Matrix Determinants using Stopped Cholesky Decomposition
Authors: Simon Bartels, Wouter Boomsma, Jes Frellsen, Damien Garreau; Published in Journal of Machine Learning Research, 24(71):1−57, 2023.
Abstract
Many algorithms involving Gaussian processes or determinantal point processes require the computation of the determinant of a kernel matrix. Traditionally, the determinant is computed using the Cholesky decomposition, which has a cubic complexity in terms of the matrix size. In this study, we propose a method to estimate the determinant using only a sub-matrix, while guaranteeing a probabilistic bound on the relative error. We present an enhanced version of the Cholesky decomposition that stops under certain conditions, thereby avoiding the need to process the entire matrix. Experimental results demonstrate significant time savings, with an overhead of less than 5% when the early stopping is not used. Additionally, we introduce a probabilistic stopping strategy for approximating a sum of known length, where the addends are revealed sequentially. Our approach does not assume independence between the addends, but only requires that they are bounded from below and decrease in conditional expectation.
[abs]