Hutch++: Optimal Stochastic Trace Estimation

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff

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


    We study the problem of estimating the trace of a matrix A that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a (1±ε) approximation to tr(A) for any positive semidefinite (PSD) A using just O(1/ε) matrix-vector products. This improves on the ubiquitous Hutchinson’s estimator, which requires O(1/ε2) matrix-vector products. Our approach is based on a simple technique for reducing the variance of Hutchinson’s estimator using a low-rank approximation step, and is easy to implement and analyze. Moreover, we prove that, up to a logarithmic factor, the complexity of Hutch++ is optimal amongst all matrix-vector query algorithms, even when queries can be chosen adaptively. We show that it significantly outperforms Hutchinson’s method in experiments. While our theory requires A to be positive semidefinite, empirical gains extend to applications involving non-PSD matrices, such as triangle estimation in networks.

    Original languageEnglish (US)
    Title of host publication4th Symposium on Simplicity in Algorithms, SOSA 2021
    EditorsValerie King, Hung Viet Le
    PublisherSociety for Industrial and Applied Mathematics Publications
    Number of pages14
    ISBN (Electronic)9781713827122
    StatePublished - 2021
    Event4th Symposium on Simplicity in Algorithms, SOSA 2021, co-located with SODA 2021 - Alexandria, United States
    Duration: Jan 11 2021Jan 12 2021

    Publication series

    Name4th Symposium on Simplicity in Algorithms, SOSA 2021


    Conference4th Symposium on Simplicity in Algorithms, SOSA 2021, co-located with SODA 2021
    Country/TerritoryUnited States

    ASJC Scopus subject areas

    • Computational Theory and Mathematics
    • Computational Mathematics
    • Numerical Analysis
    • Theoretical Computer Science


    Dive into the research topics of 'Hutch++: Optimal Stochastic Trace Estimation'. Together they form a unique fingerprint.

    Cite this