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

2015/03/01 by Christos Boutsidis, Boutsidis, Christos, Petros Drineas +7 · 2 citations
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Matrix Theory and Algorithms #Stochastic Gradient Optimization Techniques #cs.DS

paper · pdf · doi:10.48550/arxiv.1503.00374

working paper

openalex publication_date 2015/03/01 · arxiv created 2016/08/31 · arxiv updated 2016/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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~\citeAT11. 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 (θ₁,1), with 0<θ₁<1; the latter setting was proposed in~\citeicml2015_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.

Cited by

• On the Equivalence of Gaussian Graphical Models Defined on Complete Bipartite Graphs
• BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions

Related

• Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time
• A preconditioning technique of Gauss--Legendre quadrature for the logarithm of symmetric positive definite matrices
• Randomized Matrix-free Trace and Log-Determinant Estimators
• Randomized block Krylov space methods for trace and log-determinant estimators
• Approximation of the determinant of large sparse symmetric positive definite matrices