Answers are grounded in this paper and cite their sources.
Analysis demonstrates that randomized block Krylov methods yield effective rank-k approximation, indicating block size's relevance.
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 + ε)-factor approximation to the best rank-k approximation can be obtained after O(k/√ε) 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(k²). Nevertheless, in practice, the performance of block Krylov methods is often optimized by choosing a block size 1 b k. We resolve this theory-practice gap by proving that randomized block Krylov iteration produces a (1 + ε)-factor approximate rank-k approximation using O(k/√ε) 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].
No takes yet. Share an insight, caveat, or question.
Chen et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: