A Tight Analysis of Hutchinson’s Diagonal Estimator

Prathamesh Dharangutte, Christopher Musco

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
    EditorsTelikepalli Kavitha, Kurt Mehlhorn
    PublisherSociety for Industrial and Applied Mathematics Publications
    Pages353-364
    Number of pages12
    ISBN (Electronic)9781611977585
    StatePublished - 2023
    Event2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023 - Florence, Italy
    Duration: Jan 23 2023Jan 25 2023

    Publication series

    NameProceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023

    Conference

    Conference2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
    Country/TerritoryItaly
    CityFlorence
    Period1/23/231/25/23

    ASJC Scopus subject areas

    • Software
    • General Mathematics

    Fingerprint

    Dive into the research topics of 'A Tight Analysis of Hutchinson’s Diagonal Estimator'. Together they form a unique fingerprint.

    Cite this