A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix

DOI10.1016/j.laa.2017.07.004zbMath1422.65071arXiv1503.00374OpenAlexW2963586518MaRDI QIDQ2404966

Petros Drineas, Eugenia-Maria Kontopoulou, Anastasios Zouzias, Prabhanjan Kambadur, Christos Boutsidis

Publication date: 21 September 2017

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.00374

zbMATH Keywords

randomized algorithmpower methodtrace estimationSPD matrixlogdeterminant approximation

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness, Randomized matrix-free trace and log-determinant estimators, On randomized trace estimates for indefinite matrices with an application to determinants, Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature, Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations, The lifetime of micron scale topological chiral magnetic states with atomic resolution, Data-driven learning of differential equations: combining data and model uncertainty, Determinant-Preserving Sparsification of SDDM Matrices, A general scheme for log-determinant computation of matrices via stochastic polynomial approximation, Faster stochastic trace estimation with a Chebyshev product identity, Randomized block Krylov subspace methods for trace and log-determinant estimators, GADE: a generative adversarial approach to density estimation and its applications, Nonintrusive approximation of parametrized limits of matrix power algorithms – application to matrix inverses and log-determinants, A multilevel approach to stochastic trace estimation, Randomized algorithms of maximum likelihood estimation with spatial autoregressive models for large-scale networks, Unnamed Item

Uses Software

• SparseMatrix
• Eigen
• WSMP
• Elemental
• glasso
• QUIC
• CSparse

Cites Work

• Unnamed Item
• Sparse inverse covariance estimation with the graphical lasso
• Log-det approximation based on uniformly distributed seeds and its application to Gaussian process regression
• Chebyshev approximation of log-determinants of spatial weight matrices
• The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices
• Monte Carlo estimates of the log determinant of large sparse matrices
• Randomized matrix-free trace and log-determinant estimators
• Approximation of the Determinant of Large Sparse Symmetric Positive Definite Matrices
• The university of Florida sparse matrix collection
• Dense Model Theorems and Their Applications
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Approximations to the determinant term in gaussian maximum likelihood estimation of some spatial models
• Elemental
• Direct Methods for Sparse Linear Systems
• Approximate implementation of the logarithm of the matrix determinant in Gaussian process regression
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• First-Order Methods for Sparse Covariance Selection
• Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations