A structural bound for cluster robustness of randomized small-block Lanczos
For researchers in numerical linear algebra, this work provides a theoretical foundation for the cluster robustness of RSBL, which was previously lacking, though the results are partially conjectural and incremental.
The paper addresses the lack of cluster robustness in the Lanczos method for symmetric eigenvalue problems and proposes a structural bound for the Randomized Small-Block Lanczos (RSBL) method. The authors develop a theoretical bound using matrix polynomials and validate a conjectured probabilistic bound through empirical experiments.
The Lanczos method is a fast and memory-efficient algorithm for solving large-scale symmetric eigenvalue problems. However, its rapid convergence can deteriorate significantly when computing clustered eigenvalues due to a lack of cluster robustness. A promising strategy to enhance cluster robustness -- without substantially compromising convergence speed or memory efficiency -- is to use a random small-block initial, where the block size is greater than one but still much smaller than the cluster size. This leads to the Randomized Small-Block Lanczos (RSBL) method. Despite its empirical effectiveness, RSBL lacks the comprehensive theoretical understanding already available for single-vector and large-block variants. In this paper, we develop a structural bound that supports the cluster robustness of RSBL by leveraging tools from matrix polynomials. We identify an intrinsic theoretical challenge stemming from the non-commuting nature of matrix multiplication. To provide further insight, we propose a conjectured probabilistic bound for cluster robustness and validate it through empirical experiments. Finally, we discuss how insights into cluster robustness can enhance our understanding of RSBL for both eigenvalue computation and low-rank approximation.