Pure relative error for approximation by a linear matrix family
Let $n \ge 1$ and $1 \le q \le n^2$, let $P_1, \dots, P_q \in \mathbb{R}^{n \times n}$ be linearly independent matrices, given explicitly, and let $\mathcal L$ be their real span. 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 may choose its queries adaptively, and computation between queries is unrestricted; it works in exact real arithmetic, with comparisons, standard Gaussian samples and exact singular value decompositions as primitives. 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, for any $\alpha, \varepsilon \in (0, 1)$, returns $B \in \mathcal L$ with $$\|A - B\|_F \le (3 + \varepsilon)\min_{D \in \mathcal L}\|A - D\|_F + \alpha\|A\|_F$$ with high probability, using $\tilde O(\sqrt{q\log(1/\alpha)}/\varepsilon^2)$ queries, where $\tilde O$ hides polylogarithmic factors. They note that $(1 + \varepsilon)$ relative error, without the additive term, can be obtained with $O(q/\varepsilon)$ queries of $A$ alone. For approximation by matrices with a fixed sparsity pattern having at most $s$ entries in each row, $O(s/\varepsilon)$ nonadaptive queries of $A$ give $(1 + \varepsilon)$ relative error with constant probability (Amsel, Chen, Duman Keles, Halikias, Musco and Musco).
Problem. Are there absolute constants $C > 0$ and integers $a, b \ge 0$, and a single randomized algorithm that, for all $n$, $q$ and $P_1, \dots, P_q$ as above, every $A \in \mathbb{R}^{n \times n}$ and every $0 < \varepsilon < 1/2$, makes at most $$C\sqrt q\,\varepsilon^{-a}\bigl[1 + \log(2 + q) + \log(1/\varepsilon)\bigr]^b$$ queries and returns $c_1, \dots, c_q \in \mathbb{R}$ with $$\Pr\Bigl[\Bigl\|A - \sum_{j=1}^q c_jP_j\Bigr\|_F \le (1 + \varepsilon)\min_{D \in \mathcal L}\|A - D\|_F\Bigr] \ge 0.99?$$
Source: Amsel, Avi, Chen, Duman Keles, Hegde, Musco, Musco and Persson (2026), the conjecture in their Open Problems section (§4 of the COLT version, §5 of arXiv:2507.19290) that Õ(√q/poly(ε)) queries suffice for pure (1 + ε) relative error; stated in this form by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- matrix-vector queries, OpenProblemsInNLA, query complexity, structured matrices
- 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},
}
@article{amsel2026fixed,
author = {Amsel, Noah and Chen, Tyler and Duman Keles, Feyza and Halikias, Diana and Musco, Cameron and Musco, Christopher},
title = {Fixed-Sparsity Matrix Approximation from Matrix-Vector Products},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {47},
number = {2},
year = {2026},
pages = {483--511},
doi = {10.1137/25M1742710},
eprint = {2402.09379},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-re05,
author = {Townsend, Alex},
title = {{RE-05}: Pure relative error for approximation by a linear matrix family},
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-05/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
We give a self-contained proof that a known $q$-dimensional linear matrix family can be fitted to an unknown matrix with pure relative Frobenius error using nonadaptive, two-sided matrix–vector queries. The algorithm measures a high-leverage left subspace exactly and uses a Gaussian right sketch on its orthogonal complement. Only a lower bound on the sketched Gram matrix is required. A second-moment …
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-00246, "Pure relative error for approximation by a linear matrix family", clopen.solutions.