{"ID":2884854,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.06486","arxiv_id":"2508.06486","title":"Does block size matter in randomized block Krylov low-rank approximation?","abstract":"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/\\sqrt{\\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(k^2)$. 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/\\sqrt{\\varepsilon})$ matrix-vector products for any block size $1\\le b\\le 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 \u0026 Vempala, SODA 2021; Nie, STOC 2022].","short_abstract":"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/\\sqrt{\\varepsilon})$ matrix-vector...","url_abs":"https://arxiv.org/abs/2508.06486","url_pdf":"https://arxiv.org/pdf/2508.06486v2","authors":"[\"Tyler Chen\",\"Ethan N. Epperly\",\"Raphael A. Meyer\",\"Christopher Musco\",\"Akash Rao\"]","published":"2025-08-08T17:50:01Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.NA\"]","methods":"[]","has_code":false}