TY - GEN
T1 - A Tight Analysis of Hutchinson’s Diagonal Estimator
AU - Dharangutte, Prathamesh
AU - Musco, Christopher
N1 - Publisher Copyright:
Copyright © 2023 by SIAM.
PY - 2023
Y1 - 2023
N2 - Let A ∈ Rn×n be a matrix with diagonal diag(A) ∈ Rn. We show that the simple and practically popular Hutchinson’s estimator, run for m trials, returns a diagonal estimate d̃ ∈ Rn such that with probability 1 − δ, ∥d̃− diag(A)∥2 ≤ cr log(2m /δ) ∥Ā∥F . Above c is a fixed constant and Ā equals A with its diagonal set to zero. This result improves on recent work in [4] by a log(n) factor, yielding a bound that is independent of the matrix dimension, n. We show a similar bound for variants of Hutchinson’s estimator that use non-Rademacher random vectors.
AB - Let A ∈ Rn×n be a matrix with diagonal diag(A) ∈ Rn. We show that the simple and practically popular Hutchinson’s estimator, run for m trials, returns a diagonal estimate d̃ ∈ Rn such that with probability 1 − δ, ∥d̃− diag(A)∥2 ≤ cr log(2m /δ) ∥Ā∥F . Above c is a fixed constant and Ā equals A with its diagonal set to zero. This result improves on recent work in [4] by a log(n) factor, yielding a bound that is independent of the matrix dimension, n. We show a similar bound for variants of Hutchinson’s estimator that use non-Rademacher random vectors.
UR - http://www.scopus.com/inward/record.url?scp=85153726313&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85153726313&partnerID=8YFLogxK
U2 - 10.1137/1.9781611977585.ch32
DO - 10.1137/1.9781611977585.ch32
M3 - Conference contribution
AN - SCOPUS:85153726313
T3 - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
SP - 353
EP - 364
BT - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
A2 - Kavitha, Telikepalli
A2 - Mehlhorn, Kurt
PB - Society for Industrial and Applied Mathematics Publications
T2 - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
Y2 - 23 January 2023 through 25 January 2023
ER -