PaperlayerView exact revision on arXiv

Source-linked AI summary

Hutch#: Optimal non-adaptive Frobenius norm estimation

Tyler Chen, Diana Halikias, Christopher Musco, David Persson

arXiv:2609.28472v1math.NAcs.DScs.NA

TL;DR

Frobenius norm estimation has an optimal O(1/ε) query bound when adaptivity is allowed, prompting the question of whether non-adaptive methods can attain it. Hutch# is a non-adaptive estimator using products with A and A^T, while experiments report that its spectrum-aware variant outperforms vanilla Hutch# and Girard–Hutchinson.

  • Problem

    The question is whether non-adaptive methods can match the O(1/ε) complexity known to be optimal for Frobenius norm estimation.

    Source: §1 · p. 2

  • Method

    Hutch# uses 2r non-adaptive matrix-vector products with A and A^T, without orthogonalization or a pseudoinverse.

    Source: §1.1 · p. 2

  • Results

    The spectrum-aware estimator universally outperforms vanilla Hutch# and Girard–Hutchinson in experiments.

    Source: §1.2 · p. 4

  • Takeaways & Limitations

    Hutch# pairs non-adaptive products with a simple implementation that avoids advanced linear-algebra kernels.

    Source: §1.1 · p. 2

    Hutch# does not always outperform Girard–Hutchinson.

    Source: §3 · p. 5

Abstract

from arXiv · show

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 $\Omega$ is a random Gaussian matrix with $r = O(1/\varepsilon^2)$ columns, than $\frac{1}{r}\|A\Omega\|_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\Omega\|_F^2 + \frac{1}{r}\|\Psi^T A\|_F^2 - \frac{1}{r^2}\|\Psi^T A\Omega\|_F^2}, \end{align*} where $\Psi$ 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++.

1 Introduction

Frobenius norm estimation arises in several matrix-approximation and optimization tasks, and this section asks whether non-adaptive queries can attain optimal complexity. It introduces Hutch# and related variants that aim to combine that query efficiency with simple, non-adaptive computation.

1 Introduction

  • Frobenius norm estimation supports matrix-approximation error estimates, implicit Jacobian and Hessian norms in optimization, and learning structured linear operators.The passage also lists sparse approximations and other applications.Source: §1 · p. 1
  • The Girard–Hutchinson estimator needs r = O(1/ε^2) for variance on the order of ε^2∥A∥_F^4 and gives a high-probability approximation.Its simplicity comes from choosing all random vectors upfront; non-adaptive products can also be useful in parallel, distributed, and streaming settings.Source: §1 · p. 2

1.1 An Optimal, Non-Adaptive Method

  • Hutch# uses two Gaussian sketches and 2r non-adaptive products with A and A^T, without orthogonalization or a pseudoinverse.Its crude low-rank approximation suffices to match Hutch++'s optimal rate for this estimation task.Source: §1.1 · pp. 2–3
  • O(1/ε) queries suffice for Hutch# to achieve the multiplicative guarantee, matching the optimal complexity for Frobenius norm estimation.The paper identifies this as its main theoretical result.Source: §1.1 · p. 3

1.2 Additional Results

  • The weighted family interpolates between Hutch# and a symmetrized Girard–Hutchinson estimator, while its spectrum-aware variant estimates R from the same sketches.Experiments report that the spectrum-aware estimator outperforms vanilla Hutch# and Girard–Hutchinson in all cases.Source: §1.2 · pp. 3–4
  • Hutch♭ uses a generalized Nyström approximation non-adaptively and can achieve much lower variance when A’s singular values decay rapidly.It requires more postprocessing than Hutch#, including a pseudoinverse.Source: §1.2 · p. 4

1.3 Notation

  • The Schatten-4 norm provides a measure of spectral flatness, ranging from equality with the Frobenius norm at rank one to a value tied to the number of equal nonzero singular values.The notation section presents this quantity as a way to describe the flatness of A’s spectrum.Source: §1.3 · p. 4

2 Main Analysis

The analysis establishes unbiasedness and bounds the estimator’s variance, then uses that bound to derive probability and query guarantees. It also describes a median-of-means option for improving the failure-probability dependence.

2 Main Analysis

  • Applying the law of total variance to H#_r(A) organizes the variance analysis after unbiasedness is established.The proof invokes Fact 2.1 for unbiasedness and proceeds to compute variance.Source: §2 · pp. 4–5
  • The inequality ∥A∥_(4) ≤ ∥A∥F supplies the final step in the stated variance-bound result.Source: §2 · p. 5
  • Chebyshev’s inequality converts the variance bound into probability guarantees, with the required query count depending on failure probability δ.Source: §2 · p. 5
  • The median-of-means trick improves the failure-probability dependence to log(1/δ) using independent Hutch# runs.The passage specifies O(log(1/δ)) runs, each with r = O(1/ε).Source: §2 · p. 5

3 An Improved Weighted Estimator

The section introduces a convex combination of Girard–Hutchinson and Hutch# with variance below either endpoint. It then describes a non-adaptive practical route to approximate the weight, while noting an unresolved analysis concern about reusing a sketch.

3 An Improved Weighted Estimator

  • Hutch# improves the error dependence over Girard–Hutchinson, but does not always outperform it.Source: §3 · p. 5
  • The optimized convex combination has smaller variance than both Girard–Hutchinson and Hutch#.The estimator interpolates between the two, and its variance is minimized at α* = 1/(1+2T).Source: §3 · pp. 5–6

3.1 Practical Implementation

  • Because α* is not efficiently computable, the implementation approximates the quantities needed to set it using non-adaptive matvecs.With r = O(1), the described estimators give a constant-factor approximation to ∥A∥_(4) with constant probability.Source: §3.1 · p. 6
  • The experiments reuse AΩ to estimate ∥A∥_(4), although ensuring this reuse causes no dependency issues would require additional theoretical work.The authors report no apparent experimental issues from the reuse.Source: §3.1 · p. 7

4 An Estimator Based on the Generalized Nystr¨om Method

Hutch♭ uses a generalized Nyström approximation to build a non-adaptive Frobenius-norm estimator, trading some simplicity for potential gains on rapidly decaying spectra. Its variance guarantee supports relative-error estimation, and the bound can tighten when the spectrum decays.

4 An Estimator Based on the Generalized Nystr¨om Method

  • Hutch♭ uses generalized Nyström approximation with non-adaptive products, sacrificing some simplicity but potentially performing better on rapidly decaying spectra.Source: §4 · p. 7
  • The estimator uses three Gaussian sketches and requires 4r non-adaptive products with each of A and A^T.BG is computable directly from AΩ, Ψ^T A, and AG.Source: §4 · p. 7
  • Hutch♭ is unbiased, and setting r = O(1/ε) yields variance at most ε²∥A∥_F^4 and a high-probability relative-error approximation.Source: §4 · p. 8
  • The variance bound can be much tighter when A has spectral decay, and Hutch♭ often outperforms Hutch# for that reason.Source: §4 · p. 8, §4.1 · p. 8

4.1 Analysis

  • The analysis bounds the approximation error ∥A^T A − B^T B∥_2 for the generalized Nyström low-rank approximation B.The authors state that this lemma suffices to prove the main result.Source: §4.1 · p. 8

5 Numerical experiments

Across the tested spectra, adaptive Hutch++ and Nyström++ typically had the lowest error, while Hutch♭ outperformed Hutch# with sufficient spectral decay. For non-adaptive methods, weighted Hutch# uniformly outperformed Hutch# and Hutchinson’s in the tested settings.

5.1 Hutch# and Weighted Hutch#

  • Hutch# variance showed improved 1/r^2 scaling versus Hutchinson’s 1/r scaling, and Hutch# significantly outperformed Hutchinson’s on matrices with spectral decay.Hutchinson’s could perform better for flatter spectra, most evidently at c = 0.5.Source: §5.1 · p. 10
  • Weighted Hutch# uniformly outperformed Hutch# and Hutchinson’s for every tested matrix and target number of matvecs.Figure 1 reports normalized RMSE over 200 trials against the number of matrix-vector products.Source: Figure 1 · p. 9, §5.1 · p. 10

5.2 Hutch♭and Comparison to Hutch++

  • With sufficient spectral decay, Hutch♭ outperformed Hutch#; adaptive Hutch++ and Nyström++ typically had the lowest error for a given number of matrix-vector products.All methods tested have the same O(1/ε) worst-case matvec guarantee, though adaptive methods may be inapplicable in some settings or have higher cost per matvec.Source: Figure 2 · p. 10, §5.2 · p. 11

5.1 Hutch# and Weighted Hutch#

  • The implemented weighted estimator reused its Gaussian sketch to estimate the mixing parameter, with negligible performance difference from using the optimal parameter α∗.This suggests sketch reuse found a near-optimal mixing parameter in the tested cases.Source: §5.1 · p. 11

5. Numerical experiments

  • The experiments used 1000 × 1000 diagonal matrices with polynomial or exponential spectral decay and reported normalized RMSE over 200 trials.The Hutch♭ comparison tested polynomial decay at c ∈ {0.25, 1, 4} and exponential decay σj = exp(−0.05(j − 1)).Source: §5.1 · pp. 9–10, §5.2 · p. 11

A Proof of the Generalized Nystr¨om Error Bound

The proof of Lemma 4.2 decomposes the approximation error, bounds its terms, and combines the resulting inequalities to prove the stated bound.

A Proof of the Generalized Nystr¨om Error Bound

Loading 2609.28472v1…