# Does block size matter in randomized block Krylov low-rank approximation?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2025.

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

- [Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation](https://mlsanity.com/paper/2605.09755/) (2026)

## Abstract (arXiv)

We study the problem of computing a rank-k approximation of a matrix using randomized block Krylov iteration. Prior work has shown that, for block size b = 1 or b = k, a (1 + varepsilon)-factor approximation to the best rank-k approximation can be obtained after tilde O(k/√varepsilon) matrix-vector products with the target matrix. On the other hand, when b is between 1 and k, the best known bound on the number of matrix-vector products scales with b(k-b), which could be as large as O(k2). Nevertheless, in practice, the performance of block Krylov methods is often optimized by choosing a block size 1 ll b ll k. We resolve this theory-practice gap by proving that randomized block Krylov iteration produces a (1 + varepsilon)-factor approximate rank-k approximation using tilde O(k/√varepsilon) matrix-vector products for any block size 1≤ b≤ k. Our analysis relies on new bounds for the minimum singular value of a random block Krylov matrix, which may be of independent interest. Similar bounds are central to recent breakthroughs on faster algorithms for sparse linear systems [Peng & Vempala, SODA 2021; Nie, STOC 2022].