Nonadaptive queries for finite-family matrix approximation
Let $n \ge 1$, let $\mathcal F \subset \mathbb{R}^{n \times n}$ be a finite family, given explicitly, with $M = |\mathcal F| \ge 2$, and let $t = \log(2M)$. An algorithm sees $A \in \mathbb{R}^{n \times n}$ only through matrix–vector queries, each returning $Av$ or $A^{\mathsf T}v$ for a real vector $v$ of its choice, and both kinds count. It works in exact real arithmetic, with comparisons, standard Gaussian samples and exact singular value decompositions as primitives, and only queries are charged: processing the family and the answers is unrestricted. Probabilities are over the algorithm's randomness, for each fixed input.
Amsel, Avi, Chen, Duman Keles, Hegde, Musco, Musco and Persson gave an algorithm that returns $B \in \mathcal F$ with $\|A - B\|_F \le (3 + \varepsilon)\min_{D \in \mathcal F}\|A - D\|_F$ with high probability using $\tilde O(\sqrt{\log M}/\varepsilon^2)$ queries, where $\tilde O$ hides polylogarithmic factors. Its queries to $A^{\mathsf T}$ are chosen in advance, but its queries to $A$ depend on earlier answers. They showed that some families need $\Omega(\sqrt{\log M})$ queries for any constant approximation factor, even with adaptive queries, and note that the best nonadaptive method known to them uses $\tilde O(\log M/\varepsilon^2)$ queries.
Problem. Are there an absolute constant $C > 0$, an integer $b \ge 0$ and a single randomized algorithm that, for every such $n$, $\mathcal F$ and $A$ and every $0 < \varepsilon < 1/2$, chooses all its query vectors, and for each whether to apply $A$ or $A^{\mathsf T}$, before receiving any answer, makes at most $$C\sqrt t\,\varepsilon^{-2}\bigl[1 + \log(2 + t) + \log(1/\varepsilon)\bigr]^b$$ queries, and returns $B \in \mathcal F$ with $$\Pr\Bigl[\|A - B\|_F \le (3 + \varepsilon)\min_{D \in \mathcal F}\|A - D\|_F\Bigr] \ge 0.99?$$ The query choices may depend on $\mathcal F$, $\varepsilon$ and the algorithm's randomness.
Source: Amsel, Avi, Chen, Duman Keles, Hegde, Musco, Musco and Persson (2026), who ask in their Open Problems section (§4 of the COLT version, §5 of arXiv:2507.19290) whether their bound can be achieved with query vectors chosen all at once, as does Christopher Musco's ICERM lecture of 4 February 2026 (slide 23); stated in this form by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- matrix-vector queries, nonadaptive algorithms, OpenProblemsInNLA, query complexity
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@inproceedings{amsel2026,
author = {Amsel, Noah and Avi, Pratyush and Chen, Tyler and Duman Keles, Feyza and Hegde, Chinmay and Musco, Christopher and Musco, Cameron and Persson, David},
title = {Query Efficient Structured Matrix Learning},
booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory},
series = {Proceedings of Machine Learning Research},
volume = {336},
publisher = {PMLR},
year = {2026},
pages = {158--194},
eprint = {2507.19290},
archivePrefix = {arXiv},
}
@misc{musco2026,
author = {Musco, Christopher},
title = {Structured Matrix Learning from Matrix-Vector Products},
howpublished = {Lecture slides, ICERM, Brown University},
year = {2026},
note = {4 February 2026},
url = {https://app.icerm.brown.edu/assets/568/10574/10574_5858_Musco_020420261630_Slides.pdf},
}
@misc{openproblemsinnla-re06,
author = {Townsend, Alex},
title = {{RE-06}: Nonadaptive queries for finite-family matrix 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/RE-06/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For an explicitly given finite family $\mathcal F \subset \mathbb{R}^{n \times n}$ of size $M \ge 2$ and a fixed unknown matrix $A$ accessible through products $Av$ and $A^{\mathsf T}v$, the manuscript gives a fully nonadaptive algorithm returning $\widehat B \in \mathcal F$ with $\|A - \widehat B\|_F \le (3 + \varepsilon)\min_{B \in \mathcal F}\|A - B\|_F$ with probability at …
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-00247, "Nonadaptive queries for finite-family matrix approximation", clopen.solutions.