Absolute-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 $A \in \mathbb{R}^{n \times n}$, possibly indefinite, let $\lambda = \|A\|_2$ and $\phi = \|A\|_F$ be its spectral and Frobenius norms, $\rho = \phi^2/\lambda^2$, $$B_{\lambda,\phi} = \lambda \operatorname{diag}\bigl(I_{\lfloor \rho \rfloor},\, \sqrt{\rho - \lfloor \rho \rfloor}\bigr),$$ whose last diagonal entry may be zero, and let $X$ have the Gamma distribution with shape $m\rho/2$ and rate $m/(2\lambda)$, so that $\mathbb{E}X = \phi^2/\lambda$. The estimators for $A$ and $B_{\lambda,\phi}$ use Gaussian vectors of their own dimensions; only their distributions are compared. Cortinovis and Kressner proved $$\Pr\bigl(|T_m(A) - \operatorname{tr}(A)| \ge \varepsilon\bigr) \le 2\exp\Bigl(-\frac{m\varepsilon^2}{4\phi^2 + 4\varepsilon\lambda}\Bigr)$$ 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\bigr) \le 2\Pr\bigl(T_m(B_{\lambda,\phi}) - \operatorname{tr}(B_{\lambda,\phi}) \ge \varepsilon\bigr) \le 2\Pr\Bigl(X - \frac{\phi^2}{\lambda} \ge \varepsilon\Bigr)$$ for every $n \ge 1$, every nonzero real symmetric $A \in \mathbb{R}^{n \times n}$, every integer $m \ge 1$ and every $\varepsilon \ge 2\lambda/m + \sqrt{2\phi^2/m + (2\lambda/m)^2}$?
Source: Hallman (2024), Conjecture 4: the comparison of his Theorem 7 holds for every ε ≥ 2λ/m + √(2φ²/m + (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-ra13,
author = {Townsend, Alex},
title = {{RA-13}: Absolute-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-13/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, possibly indefinite, matrix $A$ with $\lambda = \|A\|_2$, $\phi = \|A\|_F$ and $\rho = \phi^2/\lambda^2$, the manuscript proves that for every $\varepsilon \ge 2\lambda/m + \sqrt{2\phi^2/m + (2\lambda/m)^2}$ the probability $\Pr(|T_m(A) - \operatorname{tr}(A)| \ge \varepsilon)$ is at most twice the upper tail at $\varepsilon$ of the …
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-00244, "Absolute-error threshold for extremal Gaussian trace bounds", clopen.solutions.