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

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 -