{"id":"arxiv/2609.28472","url":"https://arxiv.org/abs/2609.28472","tags":["math.NA","cs.DS"],"score":0,"title":"Hutch#: Optimal non-adaptive Frobenius norm estimation","domain":"math.NA","source":"arxiv","authors":["Tyler Chen","Diana Halikias","Christopher Musco","David Persson"],"reviews":0,"subject":"math.NA","summary":"The Girard--Hutchinson estimator provides an extremely simple randomized estimate of the Frobenius norm of a matrix $A$ that can only be accessed implicitly via matrix-vector products. In particular, if $Ω$ is a random Gaussian matrix with $r = O(1/\\varepsilon^2)$ columns, than $\\frac{1}{r}\\|AΩ\\|_F^2$ provides a $(1\\pm \\varepsilon)$ multiplicative approximation to $\\|A\\|_F^2$ with high probability. In this work, we introduce a closely related estimator, given by \\begin{align*} {\\frac{1}{r}\\|AΩ\\|_F^2 + \\frac{1}{r}\\|Ψ^T A\\|_F^2 - \\frac{1}{r^2}\\|Ψ^T AΩ\\|_F^2}, \\end{align*} where $Ψ$ is a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{}}