Smoothing Splines and Rank Structured Matrices: Revisiting the Spline Kernel

We show that the spline kernel of order $p$ is a so-called semiseparable function with semiseparability rank $p$. A consequence of this is that kernel matrices generated by the spline kernel are rank structured matrices that can be stored and factorized efficiently. We use this insight to derive new recursive algorithms with linear complexity in the number of knots for various kernel matrix computations. We also discuss applications of these algorithms, including smoothing spline regression, Gaussian process regression, and some related hyperparameter estimation problems.