Does block size matter in randomized block Krylov iteration?

Randomized block Krylov iteration (RBKI) is perhaps the best algorithm we know for computing low-rank approximations and dominant singular vectors for a large matrix accessible by matrix products. Existing bounds show that RBKI achieves nearly optimal runtime scaling for rank-k approximation when executed both a large block size of k and a small block size of 1. However, in practice, the computational efficiency is often maximized by choosing the block size between these extremes, demonstrating a gap between theory in practice. This talk presents new theoretical results which justify the RBKI algorithm for any block size between 1 and k. The main technical advance is a new lower bound on the singular value of a square random block Krylov matrix.