# A Tight Analysis of Hutchinson's Diagonal Estimator

arXiv: https://arxiv.org/abs/2208.03268 · HTML: https://mlsanity.com/paper/2208.03268/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2022.

## Built on by (most cited first, 5 of 5)

- [Flow Matching with Uncertainty Quantification and Guidance](https://mlsanity.com/paper/2602.10326/) (2026)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Stochastic diagonal estimation with adaptive parameter selection](https://mlsanity.com/paper/2410.11613/) (2024)
- [Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation](https://mlsanity.com/paper/2508.04444/) (2025)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)

## Abstract (arXiv)

Let A∈ ℝn× n be a matrix with diagonal diag(A) and let barA be A with its diagonal set to all zeros. We show that Hutchinson's estimator run for m iterations returns a diagonal estimate tilded∈ ℝn such that with probability (1-δ), |tilded - diag(A)|2 ≤ c√fraclog(2/δ)m|barA|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.