Large-scale Log-determinant Computation through Stochastic Chebyshev Expansions
This addresses a bottleneck in machine learning applications such as Gaussian processes and kernel learning, offering a scalable solution for large-scale problems.
The paper tackles the problem of computing log-determinants for large matrices, which is computationally expensive with traditional methods like Cholesky decomposition, by proposing a linear-time randomized algorithm using stochastic Chebyshev expansions. The result is a method that achieves high accuracy and is orders of magnitude faster, enabling computation for matrices with tens of millions of variables.
Logarithms of determinants of large positive definite matrices appear ubiquitously in machine learning applications including Gaussian graphical and Gaussian process models, partition functions of discrete graphical models, minimum-volume ellipsoids, metric learning and kernel learning. Log-determinant computation involves the Cholesky decomposition at the cost cubic in the number of variables, i.e., the matrix dimension, which makes it prohibitive for large-scale applications. We propose a linear-time randomized algorithm to approximate log-determinants for very large-scale positive definite and general non-singular matrices using a stochastic trace approximation, called the Hutchinson method, coupled with Chebyshev polynomial expansions that both rely on efficient matrix-vector multiplications. We establish rigorous additive and multiplicative approximation error bounds depending on the condition number of the input matrix. In our experiments, the proposed algorithm can provide very high accuracy solutions at orders of magnitude faster time than the Cholesky decomposition and Schur completion, and enables us to compute log-determinants of matrices involving tens of millions of variables.