Clustered singular-value gaps in randomized block Krylov approximation
Let $A \in \mathbb{R}^{n \times d}$ have singular values $\sigma_1 \ge \sigma_2 \ge \cdots$, with $\sigma_j = 0$ for $j > \min(n, d)$, and let $[B]_k$ be a best rank-$k$ approximation of $B$, obtained by truncating its SVD. Fix integers $1 \le b \le k$, let $t = \lceil k/b \rceil$ and $k' = bt$, and suppose that $k' \le \operatorname{rank}(A)$ and $$\Delta = \min_{1 \le i \le k' - b} \frac{\sigma_i^2 - \sigma_{i+b}^2}{\sigma_i^2} > 0,$$ with $\Delta = 1$ when $k' = b$. Randomized block Krylov iteration, in exact arithmetic, draws $G \in \mathbb{R}^{n \times b}$ with independent standard Gaussian entries, takes an orthonormal basis $Z$ of $\operatorname{range}[G, (AA^{\mathsf T})G, \dots, (AA^{\mathsf T})^{q-1}G]$ and returns $\widehat A = Z[Z^{\mathsf T}A]_k$. Chen, Epperly, Meyer, Musco and Rao proved that the guarantees below, for the spectral or the Frobenius norm, hold with probability at least $1 - \delta$ when $$q = O\!\left(\frac{t}{\sqrt{\varepsilon}}\log\frac{\kappa}{\Delta'} + \frac{1}{\sqrt{\varepsilon}}\log\frac{n}{\delta\varepsilon}\right),$$ where $\Delta' = \min_{1 \le i \le k' - 1}(\sigma_i^2 - \sigma_{i+1}^2)/\sigma_i^2$ and $\kappa = \sigma_1^2/\sigma_{k'-1}^2$.
Problem. Is there an absolute constant $C$ such that for every such $A$, $b$ and $k$ and all $0 < \varepsilon, \delta < 1/2$, taking $$q = \left\lceil C\left[\frac{t}{\sqrt{\varepsilon}}\log\frac{2}{\Delta} + \frac{1}{\sqrt{\varepsilon}}\log\frac{n}{\delta\varepsilon}\right]\right\rceil$$ gives, with probability at least $1 - \delta$, both $$\|A - \widehat A\|_\xi \le (1 + \varepsilon)\|A - [A]_k\|_\xi \qquad (\xi = 2, F)$$ and $\bigl|\|Av_i\|_2^2 - \sigma_i^2\bigr| \le \varepsilon\sigma_{k+1}^2$ for $i = 1, \dots, k$, where $v_1, \dots, v_k$ are the top $k$ right singular vectors of $\widehat A$, in order?
Source: Chen, Epperly, Meyer, Musco and Rao (2026; arXiv 2025), §5, who conjecture that their Theorems 1.3, 3.8 and 4.1 hold with the b-th order gap in place of the least consecutive gap and without the condition number; its gap-independent algorithmic part (Theorem 1.3), with an absolute constant, log(2/Δ) and 0 < ε, δ < 1/2, stated by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- Krylov subspace methods, low-rank approximations, OpenProblemsInNLA, singular value gaps
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@inproceedings{chen2026,
author = {Chen, Tyler and Epperly, Ethan N. and Meyer, Raphael A. and Musco, Christopher and Rao, Akash},
title = {Does block size matter in randomized block {K}rylov low-rank approximation?},
booktitle = {Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {SIAM},
year = {2026},
pages = {1026--1046},
doi = {10.1137/1.9781611978971.42},
eprint = {2508.06486},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra04,
author = {Townsend, Alex},
title = {{RA-04}: Clustered singular-value gaps in randomized block Krylov approximation},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/RA-04/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For randomized block Krylov iteration with block size $b$, a Gaussian starting block and output $Z[Z^{\mathsf T}A]_k$, the manuscript proves that $q = \lceil C\varepsilon^{-1/2}(t\log(2/\Delta) + \log(n/(\delta\varepsilon)))\rceil$ iterations, with $t = \lceil k/b \rceil$, an absolute constant $C$ and $\Delta$ the relative $b$-step gap of the leading $bt$ squared singular values (assumed positive, with $bt \le \operatorname{rank}(A)$ and $0 < …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00237, "Clustered singular-value gaps in randomized block Krylov approximation", clopen.solutions.