Luka Grubišić

Implicit trace estimation aims to approximate the trace of a matrix or linear operator accessible only through matrix-vector or operator-vector products. In the matrix setting, the Girard-Hutchinson estimator typically requires $\mathcal{O}(\varepsilon^{-2})$ products to achieve accuracy $\varepsilon$, while the variance-reduced Hutch++ algorithm reduces this sample complexity to $\mathcal{O}(\varepsilon^{-1})$ for positive semidefinite matrices.