View Abstract
Abstract: Kernel methods are used throughout statistical modeling, data science, and approximation theory. Depend-
ing on the community, they may be introduced in many different ways: through dot products of feature
maps, through data-adapted basis functions in an interpolation space, through the natural structure of a
reproducing kernel Hilbert space, or through the covariance structure of a Gaussian process. We describe
these various interpretations and their relation to each other, and then turn to the key computational bot-
tleneck for all kernel methods: the solution of linear systems and the computation of (log) determinants for
dense matrices whose size scales with the number of examples. Recent developments in linear algebra make
it increasingly feasible to solve these problems efficiently even with millions of data points. We discuss some
of these techniques, including rank-structured factorization, structured kernel interpolation, and stochastic
estimators for determinants and their derivatives. We also give a perspective on some open problems and
on approaches to addressing the constant challenge posed by the curse of dimensionality.