Abstract: There are many good methods for approximating smooth functions on an interval by interpolating data points, but only a few of these generalize well to smooth functions on a higher-dimensional space. One such method involves splines, which take on the shape of a beam (for one dimension) or a plate (for two dimensions) that passes through the data points and otherwise is at equilibrium. Computing with this approach involves a Greens function or kernel that relates a displacement of the surface at one point in space to forces experienced at another points in space. The same style of approximation appears under different guises in many areas of applied mathematics, from the statistical modeling of spatial phenomena to the methods of modern machine learning.
Unfortunately, standard algorithms for choosing and fitting of kernel approximants scale cubically with the number of input data, and so are prohibitively expensive when there are more than a few thousand data points. New algorithms are needed to address these problems in a scalable manner. In this talk, we discuss recent work on such tools, with an emphasis on the interplay between the different perspectives coming from approximation theory, statistics, and numerical linear algebra.