A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix

By Christos Boutsidis, Petros Drineas, Prabhanjan Kambadur, Anastasios Zouzias. 2015

82 citations recorded by the source corpus.

We introduce a novel algorithm for approximating the logarithm of the determinant of a symmetric positive definite (SPD) matrix. The algorithm is randomized and approximates the traces of a small number of matrix powers of a specially constructed matrix, using the method of Avron and Toledo~\cite{AT11}. From a theoretical perspective, we present additive and relative error bounds for our algorithm. Our additive error bound works for any SPD matrix, whereas our relative error bound works for SPD matrices whose eigenvalues lie in the interval $(\theta_1,1)$, with $0<\theta_1<1$; the latter setting was proposed in~\cite{icml2015_hana15}. From an empirical perspective, we demonstrate that a C++ implementation of our algorithm can approximate the logarithm of the determinant of large matrices very accurately in a matter of seconds.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Estimating the Spectral Density of Large Implicit Matrices (2018, neutral): “…knowledge, randomized polynomial-based estimates of the log determinant were ﬁrst introduced by Skilling (1989), but were later rediscovered by Bai et al. (1996) and Barry and Pace (1999) and then again by Han et al. (2015) and Boutsidis et al. (2015), albeit with more theoretical investigation.”
Scalable Log Determinants for Gaussian Process Kernel Learning (2017, methodology): “While we can approximate log determinants by existing stochastic expansions relying on matrix vector multiplications (MVMs), these approaches make assumptions, such as near-uniform eigenspectra [6], which are unsuitable in machine learning contexts.”
Exponential Family Estimation via Adversarial Dynamics Embedding (2019, methodology): “Specifically, we have Stochastic Taylor Expansion (Boutsidis et al., 2017) Recall log (1 x ) = 1 k =1 x k k , we have the Taylor expansion To avoid the matrix-matrix multiplication, we further approximate the tr ( with z as Rademacher random variables, i.e. , Bernoulli distribution with p = .”
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension (2019, methodology): “At a high level, the proof follows that of (Boutsidis et al., 2017), who present a time-efficient algorithm for approxi-”
Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximations (2016, methodology): “They use Taylor expansion in conjunction with stochastic trace estimators, and propose novel error compensation methods.”