Hutch#: Optimal non-adaptive Frobenius norm estimation
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/ε2) columns, than 1/r|AΩ|F2 provides a (1± ε) multiplicative approximation to |A|F2 with high probability. In this work, we introduce a closely related estimator, given by 1/r|AΩ|F2 + 1/r|ΨT A|F2 − 1/r2|ΨT AΩ|F2, where Ψ is a second, independent random Gaussian matrix with r columns. We prove that this estimator yields a (1±ε) multiplicative approximation to |A|F2 when r = O(1/ε), a quadratic improvement over Girard--Hutchinson. This dependence on ε 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 AT and requires no orthogonalization or other advanced linear algebra steps. Thus, Hutch# combines the simplicity of the Girard--Hutchinson estimator and the optimal query complexity of Hutch++.
Related
- Quaternion Gaussian Probes for Tensor Frobenius-Norm Estimation
- Instance-Optimal Adaptive Location Estimation via Multiscale Mid-Summaries
- Time-optimal quantum dynamics under fixed-norm generators
- PowerStep: Memory-Efficient Adaptive Optimization via ℓp-Norm Steepest Descent
- On the Homogenization of Norm and Time Optimal Controls for Parabolic Equations with Oscillating Coefficients
BibTeX
@misc{chen2026hutch,
title = {{Hutch#: Optimal non-adaptive Frobenius norm estimation}},
author = {Tyler Chen and Diana Halikias and Christopher Musco and David Persson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.28472},
eprint = {2609.28472},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28472},
}
RIS
TY - UNPB
TI - Hutch#: Optimal non-adaptive Frobenius norm estimation
AU - Tyler Chen
AU - Diana Halikias
AU - Christopher Musco
AU - David Persson
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.28472
UR - https://arxiv.org/abs/2609.28472
AB - 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/ε^2) columns, than 1/r|AΩ|_F^2 provides a (1± ε) multiplicative approximation to |A|_F^2 with high probability. In this work, we introduce a closely related estimator, given by 1/r|AΩ|_F^2 + 1/r|Ψ^T A|_F^2 − 1/r^2|Ψ^T AΩ|_F^2, where Ψ is a second, independent random Gaussian matrix with r columns. We prove that this estimator yields a (1±ε) multiplicative approximation to |A|_F^2 when r = O(1/ε), a quadratic improvement over Girard--Hutchinson. This dependence on ε 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 advanced linear algebra steps. Thus, Hutch# combines the simplicity of the Girard--Hutchinson estimator and the optimal query complexity of Hutch++.
ER -