Fast Spectrum Estimation of Some Kernel Matrices
For data scientists needing to assess low-rank approximation feasibility of kernel matrices, this framework offers a computationally cheaper alternative to full eigenvalue decomposition.
This work introduces a framework to estimate eigenvalue quantiles of kernel matrices without constructing the full matrix, providing meaningful bounds for all eigenvalues. The method is proven effective for kernels with quick decay on uniformly-distributed points, with empirical validation of accuracy.
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.