Suboptimal subspace construction for log-determinant approximation

arXiv2307.02152MaRDI QIDQ6442671FDOQ6442671

Authors: Zongyuan Han, Wenhao Li, Yixuan Huang, Sheng-Xin Zhu 

Publication date: 5 July 2023

Abstract: Variance reduction is a crucial idea for Monte Carlo simulation and the stochastic Lanczos quadrature method is a dedicated method to approximate the trace of a matrix function. Inspired by their advantages, we combine these two techniques to approximate the log-determinant of large-scale symmetric positive definite matrices. Key questions to be answered for such a method are how to construct or choose an appropriate projection subspace and derive guaranteed theoretical analysis. This paper applies some probabilistic approaches including the projection-cost-preserving sketch and matrix concentration inequalities to construct a suboptimal subspace. Furthermore, we provide some insights on choosing design parameters in the underlying algorithm by deriving corresponding approximation error and probabilistic error estimations. Numerical experiments demonstrate our method's effectiveness and illustrate the quality of the derived error bounds.

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20) Numerical quadrature and cubature formulas (65D32) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Error analysis and interval analysis (65G99) Numerical computation of matrix exponential and similar matrix functions (65F60)

This page was built for publication: Suboptimal subspace construction for log-determinant approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442671)