Papers โบ Sublinear Time Eigenvalue Approximation via Random Sampling
Sublinear Time Eigenvalue Approximation via Random Sampling
Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco, Archan Ray
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We study the problem of approximating the eigenspectrum of a symmetric matrix ๐ โโ^(n รn) with bounded entries (i.e., ๐_โ โค1). We present a simple sublinear time algorithm that approximates all eigenvalues of ๐ up to additive error ยฑฯตn using those of a randomly sampled ร((logยณ n)/ฯตยณ) รร((logยณ n)/ฯตยณ) 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(๐)) and ยฑฯต๐_F when the rows of ๐ can be sampled with probabilities proportional to their sparsities or their squared โโ norms respectively. Here nnz(๐) is the number of non-zero entries in ๐ and ๐_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 ๐. We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change ยท a person checks every report against the paper or source before anything changes; decisions are listed on /corrections