MATH Seminar

Title: Estimating Kernel Matrix Eigenvalues
Seminar: Numerical Analysis and Scientific Computing
Speaker: Mikhail Lepilov of Emory University
Contact: Matthias Chung,
Date: 2023-11-02 at 10:00AM
Venue: MSC N306
Download Flyer
Kernel matrices have appeared over the past few decades as intermediate structures when computing with "big data," such as during support vector machine classification or kernel ridge regression. Naive matrix algorithms quickly become too computationally intensive once such matrices reach moderate size; in fact, even explicitly forming such matrices is undesirable when the number of points is large. Hence, various low-rank approximations to such matrices become indispensable. If the underlying points come from the real world, however, it is a priori not often clear what the numerical rank of the resulting kernel matrix is for a given tolerance: existing methods like rank-revealing QR factorization or its randomized variants only apply in the case when the full matrix to be approximated has already been formed. In this work, we attempt to approximate the spectral decay of a kernel matrix that comes from a known distribution of points by that of a smaller matrix formed by sampling a few points from a related distribution. To do so, we use only information about the distribution and the analytical properties of the kernel. We explore how and when this may yield a useful approximation of the full spectrum using various sampling schemes.

See All Seminars