A Tight Analysis of Hutchinson's Diagonal Estimator
Let ðââ^nà n be a matrix with diagonal diag(ð) and let ðĖ be ð with its diagonal set to all zeros. We show that Hutchinson's estimator run for m iterations returns a diagonal estimate dĖââ^n such that with probability (1-Îī), dĖ - diag(ð)_2 âĪ câ(log(2/Îī)/m)ðĖ _F, where c is a fixed constant independent of all other parameters. This results improves on a recent result of [Baston and Nakatsukasa, 2022] by a log(n) factor, yielding a bound that is independent of the matrix dimension n.
READ FULL TEXT