# Sublinear Time Eigenvalue Approximation via Random Sampling

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2021.

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

- [Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness](https://mlsanity.com/paper/2402.01242/) (2024)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)
- [Estimating the Spectral Moments of the Kernel Integral Operator from Finite Sample Matrices](https://mlsanity.com/paper/2410.17998/) (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)
- [Fast Length-Squared Sampling for Positive-Semidefinite Matrices](https://mlsanity.com/paper/2608.12503/) (2026)

## Abstract (arXiv)

We study the problem of approximating the eigenspectrum of a symmetric matrix mathbf A ∈ ℝn × n with bounded entries (i.e., |mathbf A|∞ ≤ 1). We present a simple sublinear time algorithm that approximates all eigenvalues of A up to additive error ± ε n using those of a randomly sampled tilde Oleft (fraclog3 nε3right ) × tilde Oleft (fraclog3 nε3right ) principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values (the magnitudes of the eigenvalues). We give improved error bounds of ± ε √nnz(A) and ± ε |mathbf A|F when the rows of mathbf A can be sampled with probabilities proportional to their sparsities or their squared ℓ2 norms respectively. Here nnz(A) is the number of non-zero entries in A and |mathbf A|F is its Frobenius norm. Even for the strictly easier problems of approximating the singular values or testing the existence of large negative eigenvalues (Bakshi, Chepurko, and Jayaram, FOCS '20), our results are the first that take advantage of non-uniform sampling to give improved error bounds. From a technical perspective, our results require several new eigenvalue concentration and perturbation bounds for matrices with bounded entries. Our non-uniform sampling bounds require a new algorithmic approach, which judiciously zeroes out entries of a randomly sampled submatrix to reduce variance, before computing the eigenvalues of that submatrix as estimates for those of mathbf A. We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice.