The conjectured relative-error threshold for Gaussian trace estimation

Let mm be the sampling number, let mu=reff(A)mu=r_{\mathrm{eff}}(A) for a nonzero symmetric positive semidefinite matrix AA, and let εrel\varepsilon_{\mathrm{rel}} be the threshold appearing in the relative-error theorem. Relative-error threshold conjecture.

εrel2mμ.\varepsilon_{\mathrm{rel}}\leq\frac{2}{m\mu}.

This would give an explicit threshold beyond which the relative-error tail bound is controlled by the corresponding Gamma random variable. The source compares it with a bound valid for all errors but does not establish the conjectured threshold.

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.