Relating Leverage Scores and Density using Regularized Christoffel Functions
Abstract
Statistical leverage scores emerged as a fundamental tool for matrix sketching and column
sampling with applications to low rank approximation, regression, random feature learning and
quadrature. Yet, the very nature of this quantity is barely understood. Borrowing ideas from the
orthogonal polynomial literature, we introduce the regularized Christoffel function associated to
a positive definite kernel. This uncovers a variational formulation for leverage scores for kernel
methods and allows to elucidate their relationships with the chosen kernel as well as population
density. Our main result quantitatively describes a decreasing relation between leverage score
and population density for a broad class of kernels on Euclidean spaces. Numerical simulations
support our findings.