Relative-error threshold for extremal Gaussian trace bounds
For a real symmetric $d \times d$ matrix $D$ and an integer $m \ge 1$, let $$T_m(D) = \frac{1}{m} \sum_{j=1}^{m} z_j^{\mathsf T} D z_j, \qquad z_1, \dots, z_m \sim N(0, I_d) \text{ independent},$$ be the Gaussian trace estimator. For a nonzero real symmetric positive semidefinite $A \in \mathbb{R}^{n \times n}$ let $\mu = \operatorname{tr}(A)/\|A\|_2 \ge 1$ be its effective rank, where $\|\cdot\|_2$ is the spectral norm, let $$B_\mu = \frac{1}{\mu} \operatorname{diag}\bigl(I_{\lfloor \mu \rfloor},\, \mu - \lfloor \mu \rfloor\bigr),$$ whose last diagonal entry may be zero, and let $X$ have the Gamma distribution with shape $m\mu/2$ and rate $m\mu/2$. The estimators for $A$ and $B_\mu$ use Gaussian vectors of their own dimensions; only their distributions are compared. Cortinovis and Kressner's tail bound gives $\Pr(|T_m(A) - \operatorname{tr}(A)| \ge \varepsilon \operatorname{tr}(A)) \le 2\exp(-m\varepsilon^2\mu/(4(1 + \varepsilon)))$ for every $\varepsilon > 0$, and Hallman proved that, for each $A$ and $m$, the two inequalities below hold for all sufficiently large $\varepsilon$.
Problem. Is $$\Pr\bigl(|T_m(A) - \operatorname{tr}(A)| \ge \varepsilon \operatorname{tr}(A)\bigr) \le \Pr\bigl(|T_m(B_\mu) - 1| \ge \varepsilon\bigr) \le \Pr\bigl(|X - 1| \ge \varepsilon\bigr)$$ for every $n \ge 1$, every nonzero real symmetric positive semidefinite $A \in \mathbb{R}^{n \times n}$, every integer $m \ge 1$ and every $\varepsilon \ge 2/(m\mu)$?
Source: Hallman (2024), Conjecture 3: the comparison of his Theorem 6 holds for every ε ≥ 2/(mμ).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR, ST
- Keywords
- Gamma distributions, OpenProblemsInNLA, tail bounds, trace estimation
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{hallman2024,
author = {Hallman, Eric},
title = {Extremal bounds for {G}aussian trace estimation},
year = {2024},
eprint = {2411.15454},
archivePrefix = {arXiv},
}
@article{cortinovis2022,
author = {Cortinovis, Alice and Kressner, Daniel},
title = {On Randomized Trace Estimates for Indefinite Matrices with an Application to Determinants},
journal = {Found. Comput. Math.},
volume = {22},
number = {3},
year = {2022},
pages = {875--903},
doi = {10.1007/s10208-021-09525-9},
eprint = {2005.10009},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra12,
author = {Townsend, Alex},
title = {{RA-12}: Relative-error threshold for extremal Gaussian trace bounds},
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-12/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For the Gaussian trace estimator $T_m$ with $m$ samples and a nonzero real symmetric positive semidefinite matrix $A$ of effective rank $\mu = \operatorname{tr}(A)/\|A\|_2$, the manuscript proves that for every $\varepsilon \ge 2/(m\mu)$ the relative-error tail $\Pr(|T_m(A) - \operatorname{tr}(A)| \ge \varepsilon \operatorname{tr}(A))$ is at most the corresponding tail for the extremal matrix $\mu^{-1}\operatorname{diag}(I_{\lfloor\mu\rfloor}, \mu - \lfloor\mu\rfloor)$, which in turn is …
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-00243, "Relative-error threshold for extremal Gaussian trace bounds", clopen.solutions.