# BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions

arXiv: https://arxiv.org/abs/2505.12289 · HTML: https://mlsanity.com/paper/2505.12289/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 18 May 2025.

## Builds on (most cited first, 15 of 15)

- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [A Review of Uncertainty Quantification in Deep Learning: Techniques, Applications and Challenges](https://mlsanity.com/paper/2011.06225/) (2020)
- [All-but-the-Top: Simple and Effective Postprocessing for Word Representations](https://mlsanity.com/paper/1702.01417/) (2017)
- [Generalized Sliced Wasserstein Distances](https://mlsanity.com/paper/1902.00434/) (2019)
- [Statistical and Topological Properties of Sliced Probability Divergences](https://mlsanity.com/paper/2003.05783/) (2020)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Sparse Cholesky factorization by Kullback-Leibler minimization](https://mlsanity.com/paper/2004.14455/) (2020)
- [Scalable Log Determinants for Gaussian Process Kernel Learning](https://mlsanity.com/paper/1711.03481/) (2017)
- [Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projections](https://mlsanity.com/paper/2106.15427/) (2021)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Sliced Wasserstein Estimation with Control Variates](https://mlsanity.com/paper/2305.00402/) (2023)
- [Optimal Sketching for Trace Estimation](https://mlsanity.com/paper/2111.00664/) (2021)
- [A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix](https://mlsanity.com/paper/1503.00374/) (2015)
- [Nonlinear Kalman Filtering with Divergence Minimization](https://mlsanity.com/paper/1705.00722/) (2017)
- [Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand](https://mlsanity.com/paper/2103.16084/) (2021)

## Built on by (most cited first, 1 of 1)

- [Uniform Approximation of Functions with Asymmetric Growth and Decay by Deep Weighted Polynomials](https://mlsanity.com/paper/2506.21306/) (2025)

## Abstract (arXiv)

Efficient matrix trace estimation is essential for scalable computation of log-determinants, matrix norms, and distributional divergences. In many large-scale applications, the matrices involved are too large to store or access in full, making even a single matrix-vector (mat-vec) product infeasible. Instead, one often has access only to small subblocks of the matrix or localized matrix-vector products on restricted index sets. Hutch++ achieves optimal convergence rate but relies on randomized SVD and assumes full mat-vec access, making it difficult to apply in these constrained settings. We propose the Block-Orthonormal Stochastic Lanczos Quadrature (BOLT), which matches Hutch++ accuracy with a simpler implementation based on orthonormal block probes and Lanczos iterations. BOLT builds on the Stochastic Lanczos Quadrature (SLQ) framework, which combines random probing with Krylov subspace methods to efficiently approximate traces of matrix functions, and performs better than Hutch++ in near flat-spectrum regimes. To address memory limitations and partial access constraints, we introduce Subblock SLQ, a variant of BOLT that operates only on small principal submatrices. As a result, this framework yields a proxy KL divergence estimator and an efficient method for computing the Wasserstein-2 distance between Gaussians - both compatible with low-memory and partial-access regimes. We provide theoretical guarantees and demonstrate strong empirical performance across a range of high-dimensional settings.