A Tight Analysis of Hutchinson's Diagonal Estimator

08/05/2022
∙
by   Prathamesh Dharangutte, et al.
∙
0
∙

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

Please sign up or login with your details

Forgot password? Click here to reset