Query complexity from Schatten to spectral norms
For $p \in [1, \infty]$ let $\|\cdot\|_{\mathcal{S}_p}$ be the Schatten $p$-norm, the $\ell_p$ norm of the singular values, so that $\|\cdot\|_{\mathcal{S}_\infty}$ is the spectral norm. Let $n \ge 2$ and $0 < \varepsilon < 1/2$. The input $A \in \mathbb{R}^{n \times n}$ is accessible only through exact products $Ax$ or $A^{\mathsf T}x$ with real vectors $x$, each costing one query. Query vectors may depend on earlier answers and on internal randomness, and computation between queries is unrestricted. Let $q_p(n, \varepsilon)$ be the least $q$ such that some algorithm making at most $q$ queries outputs a real unit vector $v$ with $$\Pr\Big[\|A(I - vv^{\mathsf T})\|_{\mathcal{S}_p} \le (1 + \varepsilon) \min_{\|u\|_2 = 1} \|A(I - uu^{\mathsf T})\|_{\mathcal{S}_p}\Big] \ge \frac{99}{100}$$ for every $A$, the probability being over the algorithm's randomness. The factor $1 + \varepsilon$ multiplies the norm, not its $p$-th power.
Bakshi, Clarkson and Woodruff gave an algorithm with $\tilde O(p^{1/6}/\varepsilon^{1/3})$ queries for $1 \le p = O(\log(n)/\varepsilon)$, where $\tilde O$ hides factors polylogarithmic in $n/\varepsilon$, and proved that for each fixed $p$ at least of order $\varepsilon^{-1/3}$ queries are needed when $n$ is large enough. For each fixed $p$, Bakshi and Narayanan proved that $O(\log(1/\varepsilon)/\varepsilon^{1/3})$ queries suffice, independently of $n$. For $p = \infty$, block Krylov iteration (Musco and Musco) uses $O(\log(n)/\sqrt{\varepsilon})$ queries, and Bakshi and Narayanan proved that $\Omega(\log(n)/\sqrt{\varepsilon})$ are needed when $n$ is at least of order $\varepsilon^{-2.01}$. Zhang, Wu, Zhang, Li, Zheng, Fang, Li and Lin report that, for $\varepsilon$ below a universal constant and success probability $2/3$, at least $c\min\{n, p^{1/6}\varepsilon^{-1/3}, \varepsilon^{-1/2}\}$ queries are needed for $2 \le p < \infty$, and $c\min\{n, \varepsilon^{-1/2}\}$ for $p = \infty$, with $c > 0$ universal.
Problem. Determine $q_p(n, \varepsilon)$ up to universal constant factors, simultaneously in $p$, $n$ and $\varepsilon$, including the transition when finite $p$ grows with $n$ or $1/\varepsilon$, the endpoint $p = \infty$, and the finite-dimensional regime, where $n$ queries reveal $A$ exactly.
Source: Bakshi and Narayanan (2023), Open Question 1.11, after Open Question 34 of Bakshi's PhD thesis (2022), which asks for the dependence on the rank, p and ε together; 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
- low-rank approximations, OpenProblemsInNLA, query complexity, Schatten norms
- 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{bakshi2022,
author = {Bakshi, Ainesh and Clarkson, Kenneth L. and Woodruff, David P.},
title = {Low-rank approximation with $1/\varepsilon^{1/3}$ matrix-vector products},
booktitle = {Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022)},
publisher = {ACM},
year = {2022},
pages = {1130--1143},
doi = {10.1145/3519935.3519988},
eprint = {2202.05120},
archivePrefix = {arXiv},
}
@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{kacham2024,
author = {Kacham, Praneeth and Woodruff, David P.},
title = {Faster Algorithms for {S}chatten-$p$ Low Rank Approximation},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
series = {LIPIcs},
volume = {317},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2024},
pages = {55:1--55:19},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.55},
eprint = {2407.11959},
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-ra15,
author = {Townsend, Alex},
title = {{RA-15}: Query complexity from Schatten to spectral norms},
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-15/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00172, "Query complexity from Schatten to spectral norms", clopen.solutions.