The conjectured absolute-error threshold for Gaussian trace estimation

Let mm be the sampling number, let λ=A2\lambda=\lVert A\rVert_2 and ϕ=AF\phi=\lVert A\rVert_F for a symmetric matrix AA, and let εabs\varepsilon_{\mathrm{abs}} be the threshold appearing in the absolute-error theorem. Absolute-error threshold conjecture.

εabs2λm+2mϕ2+(2λm)2.\varepsilon_{\mathrm{abs}}\leq\frac{2\lambda}{m}+\sqrt{\frac{2}{m}\phi^2+\left(\frac{2\lambda}{m}\right)^2}.

This would provide an explicit threshold for the absolute-error tail comparison with the extremal Gamma distribution. The source does not provide a resolution.

Sources & referencesView supporting material

Primary source

Eric Hallman, “Extremal bounds for Gaussian trace estimation”, arXiv:2411.15454 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.