Optimal query complexity of spectral rank-k approximation
Let $n \ge 2$, $1 \le k < n$ and $0 < \varepsilon < 1/2$. The input $A \in \mathbb{R}^{n \times n}$ is accessible only through exact products $Ax$ and $A^{\mathsf T}x$ with real vectors $x$, each counting as one query. Each query vector may be chosen adaptively, from all earlier answers and the algorithm's random bits, and computation between queries is unrestricted. Let $q_{\mathrm{sp}}(n, k, \varepsilon)$ be the least $q$ for which some algorithm making at most $q$ queries returns $Z \in \mathbb{R}^{n \times k}$ with $Z^{\mathsf T}Z = I_k$ such that, for every $A$, with probability at least $99/100$ over the algorithm's randomness, $$\|A(I - ZZ^{\mathsf T})\|_2 \le (1 + \varepsilon) \min_{U \in \mathbb{R}^{n \times k},\ U^{\mathsf T}U = I_k} \|A(I - UU^{\mathsf T})\|_2,$$ where $\|\cdot\|_2$ is the spectral norm. Block Krylov iteration (Musco and Musco) uses $O(k\log(n)/\sqrt{\varepsilon})$ queries. Bakshi and Narayanan proved that for $k = 1$ every algorithm needs $\Omega(\log(n)/\sqrt{\varepsilon})$ queries, on symmetric inputs, when $n$ is at least of order $\varepsilon^{-2.01}$, which makes that upper bound optimal for each fixed $k$ in this regime. Zhang, Wu, Zhang, Li, Zheng, Fang, Li and Lin report that, for $\varepsilon$ below a universal constant, every algorithm succeeding with probability $2/3$ needs at least $c\min\{n, k/\sqrt{\varepsilon}\}$ queries, with $c > 0$ universal.
Problem. Determine $q_{\mathrm{sp}}(n, k, \varepsilon)$ up to universal constant factors, simultaneously in $n$, $k$ and $\varepsilon$, including its dependence on a growing target rank $k$, rather than a fixed one, and the finite-dimensional regime, where $n$ queries reveal all columns of $A$.
Source: Bakshi and Narayanan (2023), Open Question 1.10, refining Open Question 34 of Bakshi's PhD thesis (2022), itself from Bakshi, Clarkson and Woodruff (2022), §1.2; in this form (square A, products with A and Aᵀ, success probability 99/100, 0 < ε < 1/2), OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- Krylov subspace methods, low-rank approximations, OpenProblemsInNLA, query complexity
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@inproceedings{bakshi2023,
author = {Bakshi, Ainesh and Narayanan, Shyam},
title = {Krylov Methods are (nearly) Optimal for Low-Rank Approximation},
booktitle = {2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)},
publisher = {IEEE},
year = {2023},
pages = {2093--2101},
doi = {10.1109/FOCS57990.2023.00128},
eprint = {2304.03191},
archivePrefix = {arXiv},
}
@phdthesis{bakshi2022thesis,
author = {Bakshi, Ainesh},
title = {Algorithms for Learning Latent Models: Establishing Tractability to Approaching Optimality},
school = {Carnegie Mellon University},
year = {2022},
note = {Technical report CMU-CS-22-146},
}
@inproceedings{musco2015,
author = {Musco, Cameron and Musco, Christopher},
title = {Randomized Block {K}rylov Methods for Stronger and Faster Approximate Singular Value Decomposition},
booktitle = {Advances in Neural Information Processing Systems 28 (NIPS 2015)},
publisher = {Curran Associates, Inc.},
year = {2015},
pages = {1396--1404},
eprint = {1504.05477},
archivePrefix = {arXiv},
}
@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{zhang2026,
author = {Zhang, Haihan and Wu, Wendao and Zhang, Chenheng and Li, Yanyi and Zheng, Chunyuan and Fang, Cong and Li, Haoxuan and Lin, Zhouchen},
title = {Matrix-Vector Complexity of Low-Rank Approximation},
year = {2026},
eprint = {2609.35840},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra14,
author = {Townsend, Alex},
title = {{RA-14}: Optimal query complexity of spectral rank-$k$ 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-14/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Resolution claims
An exact minimum-energy criterion characterizes when a given linear feature space contains a valid spectral rank-$k$ approximation. It includes singular tail features and unequal leading singular values. For Gaussian block-Krylov features on interpolation nodes, the criterion becomes a $k\times k$ random matrix inequality. An exact reciprocal-Gram first moment replaces an earlier product of operator-norm bounds and gives an explicit success-probability …
Two concrete pieces of the finite-accuracy transition for unrestricted adaptive matrix–vector queries are isolated, without closing the transition itself. First, a weighted Chebyshev interpolation argument proves matching bounds, for all finite parameters, for a precisely defined deterministic-width, full-block span-query class, whose query complexity is $\Theta(\min\{n,\frac{k}{\sqrt\varepsilon}\log\frac{en}{k}\})$. The lower bound uses integer spectral multiplicities, an elementary reciprocal-Gaussian-Gram moment, and a rotational argument …
For every admissible finite dimension, rank and accuracy, this note proves $q_{\mathrm{sp}}(n,k,\varepsilon)\ge c\,\frac{k}{\sqrt\varepsilon}\log\bigl(1+\frac{n\sqrt\varepsilon}{k}\bigr)$ with a universal positive constant $c$. The argument uses a determinant tilt of a singular Wishart law, its exact posterior under adaptive matrix–vector queries, and an integration-by-parts estimate on a Grassmann manifold, which bounds the growth per query of a regularized log-determinant of the hidden-kernel overlap. The …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-09 | Open → Partially resolved | The registry's curators | Finite-Accuracy Lower Bounds v1 recorded from OpenProblemsInNLA @ eb7c9d6, holden-ra14-v5-2026-09-13/report.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00171, "Optimal query complexity of spectral rank-k approximation", clopen.solutions.