Speaker
Description
In this talk we analyze an algorithm for identifying spectral gaps of a real symmetric matrix $A$ by simultaneously approximating the traces of spectral projectors associated with multiple different spectral slices. Our method utilizes Hutchinson's stochastic trace estimator together with the Lanczos algorithm to approximate quadratic forms involving spectral projectors. This approach has been already used in the literature for related problems, such as estimating the spectral density of $A$ or the number of eigenvalues in an interval; however, the currently available theoretical results are somewhat lacking in the context of detecting spectral gaps.
In this work, we focus on finding all gaps that are wider than a specified threshold and examine the problem from this perspective. By thoroughly analyzing the Hutchinson and Lanczos components of the algorithm, we obtain error bounds that allow us to determine the numbers of Hutchinson's sample vectors and Lanczos iterations needed to ensure the detection of all gaps above the target width with high probability. In particular, we conclude that the most efficient strategy is to always use a single random sample vector for Hutchinson's estimator and concentrate all computational effort in the Lanczos algorithm. Our numerical experiments demonstrate the efficiency and reliability of this approach.
This is a joint work with Michele Benzi and Michele Rinelli.
References
- Benzi, M., Rinelli, M., Simunec, I.: Estimation of spectral gaps for sparse symmetric matrices, https://arxiv.org/abs/2410.15349, (2024)
