Optimal trace-estimation complexity using Kronecker matrix-vector queries
Let $n, q \ge 2$ be integers and $0 < \varepsilon < 1/2$. The input, a real symmetric positive semidefinite $M \in \mathbb{R}^{n^q \times n^q}$, is accessible only through an exact oracle that, given $v_1, \dots, v_q \in \mathbb{R}^n$, returns $M(v_1 \otimes \cdots \otimes v_q) \in \mathbb{R}^{n^q}$. Queries may depend on earlier responses and on internal randomness, any finite exact arithmetic between calls is free, only oracle calls are counted, and $n$, $q$ and $\varepsilon$ are known. No condition number bound is imposed on the query vectors, and the estimator need not be of Hutchinson type. Let $Q(n, q, \varepsilon)$ be the least $t$ for which some randomized algorithm, for every such $M$, makes at most $t$ oracle calls and outputs $\hat t \in \mathbb{R}$ with $$\Pr\{|\hat t - \operatorname{tr}(M)| \le \varepsilon \operatorname{tr}(M)\} \ge \frac{2}{3}.$$
Meyer and Avron showed that Hutchinson's estimator, averaging $x^{\mathsf T}Mx$ over Kronecker products $x$ of independent real Gaussian vectors, achieves this guarantee with $O(3^q/\varepsilon^2)$ queries for every such $M$, and with $O((3 - 6/(n+2))^q/\varepsilon^2)$ queries when the factors are uniform on the sphere of radius $\sqrt n$, and that with factors of independent real zero-mean unit-variance entries it needs $\Omega((3 - 2/n)^q/\varepsilon^2)$ queries for some $M$ to have standard deviation at most $\varepsilon \operatorname{tr}(M)$. Meyer, Swartworth and Woodruff proved that algorithms which observe only the quadratic forms $x^{\mathsf T}Mx$, and whose query vectors form a matrix of bounded condition number, need a number of queries exponential in $q$.
Problem. Determine $Q(n, q, \varepsilon)$ up to universal constant factors, simultaneously in $n$, $q$ and $\varepsilon$.
Source: Meyer, Swartworth and Woodruff (2025), §6, who ask for tight bounds for trace estimation in the Kronecker matrix-vector model; stated as this query complexity by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR
- Keywords
- Kronecker products, OpenProblemsInNLA, query complexity, trace estimation
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@inproceedings{meyer2025,
author = {Meyer, Raphael A. and Swartworth, William and Woodruff, David P.},
title = {Understanding the {K}ronecker Matrix-Vector Complexity of Linear Algebra},
booktitle = {Proceedings of the 42nd International Conference on Machine Learning},
series = {Proc. Mach. Learn. Res.},
volume = {267},
publisher = {PMLR},
year = {2025},
pages = {43909--43933},
url = {https://proceedings.mlr.press/v267/meyer25a.html},
eprint = {2502.08029},
archivePrefix = {arXiv},
}
@article{meyer2026,
author = {Meyer, Raphael A. and Avron, Haim},
title = {Hutchinson's Estimator is Bad at {K}ronecker-Trace-Estimation},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {47},
number = {1},
year = {2026},
pages = {353--387},
doi = {10.1137/24M1720895},
eprint = {2309.04952},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra11,
author = {Townsend, Alex},
title = {{RA-11}: Optimal trace-estimation complexity using Kronecker matrix-vector queries},
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-11/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Resolution claims
We consider relative trace estimation of an arbitrary real positive-semidefinite matrix of order $N=n^q$ when an oracle returns the full matrix-vector response only on real product inputs. Two new upper bounds are established. A fractional-moment analysis of product-spherical empirical averaging, based on a convex-order domination of the normalized quadratic form by a product of scaled Beta variables, improves the fixed-accuracy …
We study relative trace estimation of arbitrary real positive-semidefinite matrices from adaptive, exact, real rank-one tensor matrix-vector queries. A degree-$q$ interpolation identity simulates one complex product query with $q+1$ real product queries. It also yields a counterexample, already for local dimension two, to Conjecture 23 of Meyer, Swartworth and Woodruff (arXiv:2502.08029v2): a fixed span of $q+1$ real product vectors has …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Unrestricted Kronecker trace estimation: polynomial real simulation, parallel factor access, and a bounded-probability lower bound v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscript/ra11_partial_results.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00170, "Optimal trace-estimation complexity using Kronecker matrix-vector queries", clopen.solutions.