Suboptimal subspace construction for log-determinant approximation

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

Publication date 5 July 2023

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

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.

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)