Estimating Traces from Noisy Matrix–Vector Products

Trace estimation for curvature, sensitivity, and second-order statistics can involve stochastic products, making the low-rank approximation used for variance reduction noisy. We determine both the optimal query cost and when spending queries on such an approximation improves accuracy. For a $d$-dimensional positive semidefinite matrix with trace in $[1,2]$, we allow adaptive unit-vector queries with fresh centered noise of total second moment at most ${\sigma }^2$ and query-direction variance at most $\rho {\sigma }^2$, where $1/d\le \rho \le 1$. At constant confidence, the minimax cost for relative error $\epsilon$ is $\Theta (\min \{d,{\epsilon }^{-1}\}+d^2\rho {\sigma }^2{\epsilon }^{-2})$. Complete correction adds the trace of the realized noisy approximation and subtracts that same approximation in every residual observation. This correction and sufficiently averaged projected estimation attain the rate, with coordinate queries in small dimensions. An exact equal-budget variance identity determines when correction improves on independent sphere sampling. Fixed noise covariance reduces the worst-case noise term to $d{\sigma }^2{\epsilon }^{-2}$. Experiments on an 81,290-parameter CNN reveal a minibatch-quality crossover. Paid decisions and a fresh-product XTrace comparison expose the cost of noisy pilots; model-score comparisons identify settings where direct model access is computationally preferable.