Hutch#: Optimal non-adaptive Frobenius norm estimation
En palabras de los autores
The Girard--Hutchinson estimator provides an extremely simple randomized estimate of the Frobenius norm of a matrix that can only be accessed implicitly via matrix-vector products. In particular, if is a random Gaussian matrix with columns, than provides a multiplicative approximation to 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 is a second, independent random Gaussian matrix with columns. We prove that this estimator yields a multiplicative approximation to when , 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 non-adaptive matrix-vector products with and 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++.
Apareció: jueves, 24 de septiembre. arXiv. Preprint, todavía sin revisión por pares.