# Optimal Eigenvalue Approximation via Sketching

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2023.

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

- [Scaling Laws in Linear Regression: Compute, Parameters, and Data](https://mlsanity.com/paper/2406.08466/) (2024)
- [Efficient Sketches for Training Data Attribution and Studying the Loss Landscape](https://mlsanity.com/paper/2402.03994/) (2024)
- [Revisiting inverse Hessian vector products for calculating influence functions](https://mlsanity.com/paper/2409.17357/) (2024)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (2025)
- [Fast Spectrum Estimation of Some Kernel Matrices](https://mlsanity.com/paper/2411.00657/) (2024)
- [What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?](https://mlsanity.com/paper/2502.07993/) (2025)
- [Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch](https://mlsanity.com/paper/2609.18577/) (2026)

## Abstract (arXiv)

Given a symmetric matrix A, we show from the simple sketch GAGT, where G is a Gaussian matrix with k = O(1/ε2) rows, that there is a procedure for approximating all eigenvalues of A simultaneously to within ε |A|F additive error with large probability. Unlike the work of (Andoni, Nguyen, SODA, 2013), we do not require that A is positive semidefinite and therefore we can recover sign information about the spectrum as well. Our result also significantly improves upon the sketching dimension of recent work for this problem (Needell, Swartworth, Woodruff FOCS 2022), and in fact gives optimal sketching dimension. Our proof develops new properties of singular values of GA for a k × n Gaussian matrix G and an n × n matrix A which may be of independent interest. Additionally we achieve tight bounds in terms of matrix-vector queries. Our sketch can be computed using O(1/ε2) matrix-vector multiplies, and by improving on lower bounds for the so-called rank estimation problem, we show that this number is optimal even for adaptive matrix-vector queries.