# Fast Spectrum Estimation of Some Kernel Matrices

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 1 Nov 2024.

## Builds on (most cited first, 12 of 12)

- [The Intrinsic Dimension of Images and Its Impact on Learning](https://mlsanity.com/paper/2104.08894/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Estimating the intrinsic dimension of datasets by a minimal neighborhood information](https://mlsanity.com/paper/1803.06992/) (2018)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Analysis of stochastic Lanczos quadrature for spectrum approximation](https://mlsanity.com/paper/2105.06595/) (2021)
- [Optimal Eigenvalue Approximation via Sketching](https://mlsanity.com/paper/2304.09281/) (2023)
- [Approximating the Spectrum of a Graph](https://mlsanity.com/paper/1712.01725/) (2017)
- [Sublinear Time Eigenvalue Approximation via Random Sampling](https://mlsanity.com/paper/2109.07647/) (2021)
- [On the Complexity of Learning with Kernels](https://mlsanity.com/paper/1411.1158/) (2014)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Moments, Random Walks, and Limits for Spectrum Approximation](https://mlsanity.com/paper/2307.00474/) (2023)
- [Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method](https://mlsanity.com/paper/2204.01941/) (2022)

## Abstract (arXiv)

In data science, individual observations are often assumed to come independently from an underlying probability space. Kernel matrices formed from large sets of such observations arise frequently, for example during classification tasks. It is desirable to know the eigenvalue decay properties of these matrices without explicitly forming them, such as when determining if a low-rank approximation is feasible. In this work, we introduce a new eigenvalue quantile estimation framework for some kernel matrices. This framework gives meaningful bounds for all the eigenvalues of a kernel matrix while avoiding the cost of constructing the full matrix. The kernel matrices under consideration come from a kernel with quick decay away from the diagonal applied to uniformly-distributed sets of points in Euclidean space of any dimension. We prove the efficacy of this framework given certain bounds on the kernel function, and we provide empirical evidence for its accuracy. In the process, we also prove a general interlacing-type theorem for finite sets of numbers. Additionally, we indicate an application of this framework to the study of the intrinsic dimension of data, as well as several other directions in which to generalize this work.