Fast Approximate Determinants Using Rational Functions

Abstract

We show how rational function approximations to the logarithm, such as $\log z\approx (z^2-1)/(z^2+6z+1)$, can be turned into fast algorithms for approximating the determinant of a very large matrix. We empirically demonstrate that when combined with a good preconditioner, the third order rational function approximation offers a very good trade-off between speed and accuracy when measured on matrices coming from Matérn-$5/2$ and radial basis function Gaussian process kernels. In particular, it is significantly more accurate on those matrices than the state-of-the-art stochastic Lanczos quadrature method for approximating determinants while running at about the same speed.

22 pages, 17 figures