Simple method halves effort for estimating matrix size measures
Hutch#: Optimal non-adaptive Frobenius norm estimation
Data Structures and Algorithms
Summary
Measuring the size of a matrix, called the Frobenius norm, is important in many computer tasks but can be slow when the matrix is very large. The authors introduce a new method called Hutch# that uses randomness in a clever way to estimate this size twice as efficiently as before, requiring fewer steps. Their approach is simple, avoids complicated calculations, and achieves the best possible speed for this kind of problem. This makes it easier and faster to work with large matrices when only certain operations are possible.
What this means in practice
- •For machine learning engineers: Estimate large matrix norms quickly when only matrix-vector multiplications are feasible, speeding up training and optimization workflows.
- •For scientific computing teams: Improve performance of large-scale simulations by efficiently estimating matrix size metrics without expensive adaptive computations.
Authors
Tyler Chen, Diana Halikias, Christopher Musco, David Persson
Abstract
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 second, independent random Gaussian matrix with $r$ columns. We prove that this estimator yields a $(1\pm\varepsilon)$ multiplicative approximation to $\|A\|_F^2$ when $r = O(1/\varepsilon)$, a quadratic improvement over Girard--Hutchinson. This dependence on $\varepsilon$ 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 \textit{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++.