A Tight Analysis of Hutchinson's Diagonal Estimator
Not on the map. Why?
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.
Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). First posted on arXiv 5 Aug 2022.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2023: 1; 2024: 1; 2025: 2; 2026: 1.
5 papers.
- 2026Flow Matching with Uncertainty Quantification and Guidancecited by 4
- 2023Krylov Methods are (nearly) Optimal for Low-Rank Approximationcited by 2
- 2024Stochastic diagonal estimation with adaptive parameter selectioncited by 1
- 2025Matrix-Free Two-to-Infinity and One-to-Two Norms Estimationcited by 1
- 2025Query Efficient Structured Matrix Learningcited by 0
- 2026Flow Matching with Uncertainty Quantification and Guidance10 Feb 2026
- 2025Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation6 Aug 2025
- 2025Query Efficient Structured Matrix Learning25 Jul 2025
- 2024Stochastic diagonal estimation with adaptive parameter selection15 Oct 2024
- 2023Krylov Methods are (nearly) Optimal for Low-Rank Approximation6 Apr 2023