Optimal Sketching for Trace Estimation

Shuli Jiang, Hai Pham, David P. Woodruff +2

Matrix trace estimation is ubiquitous in machine learning applications and has traditionally relied on Hutchinson's method, which requires $O(\log (1/\delta )/{\epsilon }^2)$ matrix-vector product…