An analysis on stochastic Lanczos quadrature with asymmetric quadrature nodes
For researchers and practitioners computing traces of matrix functions, this work offers a principled method to allocate computational resources between Monte Carlo and Lanczos steps, improving efficiency.
This paper resolves a theoretical discrepancy in Stochastic Lanczos Quadrature (SLQ) regarding affine transformations and introduces an optimized error reallocation technique for log-determinant estimation that minimizes matrix-vector multiplications, achieving tighter theoretical bounds and providing a rule-of-thumb for parameter configuration.
This paper revisits the error analysis of the Stochastic Lanczos Quadrature (SLQ) method for approximating the trace of matrix functions, with a specific focus on asymmetric Lanczos quadrature rules. We reexplain an existing theoretical discrepancy regarding the necessity of a scaling factor when applying an affine transformation from the reference interval to the physical spectral interval. Furthermore, we introduce an optimized error reallocation technique for log-determinant estimation. Rather than evenly splitting the error tolerance between the Hutchinson trace estimator and the Lanczos quadrature, we formulate an optimization problem to strategically distribute the error budget. This approach minimizes the total number of matrix-vector multiplications (MVMs) required to reach a target accuracy for both Rademacher and Gaussian queries. Numerical experiments validate that this reallocation yields tighter theoretical bounds and provides a concrete rule-of-thumb for parameter configuration: to achieve a target accuracy efficiently, more computational resources should be allocated to the Lanczos process (larger m) rather than Monte Carlo sampling (smaller N).