Hutch#: Optimal non-adaptive Frobenius norm estimation

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 $\mathrm{\Omega }$ is a random Gaussian matrix with $r=O(1\mathrm{/}{\epsilon }^2)$ columns, than $\frac{1}{r}\mathrm{\parallel }A\mathrm{\Omega }{\mathrm{\parallel }}_F^2$ provides a $(1\pm \epsilon )$ multiplicative approximation to $\mathrm{\parallel }A{\mathrm{\parallel }}_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 $\mathrm{\Psi }$ is a second, independent random Gaussian matrix with $r$ columns. We prove that this estimator yields a $(1\pm \epsilon )$ multiplicative approximation to $\mathrm{\parallel }A{\mathrm{\parallel }}_F^2$ when $r=O(1\mathrm{/}\epsilon )$, a quadratic improvement over Girard–Hutchinson. This dependence on $\epsilon$ is optimal. Our method, which we call Hutch# (pronounced ``Hutch sharp’'), matches the complexity of the Hutch++ algorithm [Meyer, Musco, Musco, Woodruff, 2021]. However, unlike Hutch++, Hutch# uses only $\mathit{\text{non-adaptive}}$ matrix-vector products with $A$ and $A^T$ and requires no orthogonalization or other adaptive linear algebra steps. Thus, Hutch# combines the simplicity of the Girard–Hutchinson estimator and the optimal query complexity of Hutch++.