Piecewise linear interpolation via kernels

Toni Karvonen, Gabriele Santin, Tizian Wenzel

Linear interpolation is one of the first tools any student of numerical analysis learns. It’s simple, intuitive, and robust. But what if we looked at this classical technique through the lens of modern Reproducing Kernel Hilbert Space (RKHS) theory?

In their recent paper, "Piecewise linear interpolation via kernels," Toni Karvonen, Gabriele Santin, and Tizian Wenzel do exactly that. They show that the humble linear spline is actually an optimal "kernel interpolant" in a specific Sobolev space, allowing them to apply advanced machinery like superconvergence theory to a problem we thought we already fully understood.

TL;DR

This paper bridges the gap between classical linear splines and modern kernel methods. By constructing specific inner products for Sobolev spaces, the authors prove that piecewise linear interpolation is a form of kernel interpolation, allowing them to use modern "superconvergence" tools to recover and unify classical error rates.

What Problem Does This Paper Address?

For decades, numerical analysis has treated splines (piecewise polynomials) and kernels (functions defining a Hilbert space) as related but often distinct families. While it was known that some splines are kernels, a systematic treatment of piecewise linear interpolation using the full weight of modern kernel theory was missing.

The challenge is that "standard" kernel methods often assume a high degree of smoothness or specific boundary conditions. The authors wanted to see if the modern framework of kernel-based superconvergence—which describes how approximations get better when the target function is smoother than the underlying space requires—could be applied to the simplest case: the linear spline.

Methods

The authors' approach follows a clear theoretical pipeline:

  1. Defining the Space: They equip the Sobolev space $W_2^1(0, 1)$ (functions with one square-integrable derivative) with a specific bilinear form that includes boundary terms.
  2. Constructing the Kernel: They derive the explicit Reproducing Kernel for this space. They define a "2-piecewise linear" kernel as one that is affine on the intervals $[0, x]$ and $[x, 1]$.
  3. The PDE Connection: They prove that these kernels are actually Green kernels for a specific second-order ordinary differential equation (ODE) with Robin-style boundary conditions.
  4. Superconvergence: Using the relationship between the kernel and the differential operator, they apply "superconvergence" theory. This allows them to derive error bounds for functions that are smoother than the $W_2^1$ space (specifically functions in $W_2^s$ for $s \in [1, 2]$).

Datasets

Not discussed in the paper. As a theoretical work in numerical analysis, the paper relies on mathematical proofs and derivations rather than empirical benchmarks on specific datasets.

Key Insights and Ideas

  • The "Aha" Moment for Splines: The authors prove that if a kernel is "2-piecewise linear," its interpolant is guaranteed to be the standard piecewise linear interpolant (linear spline). This provides a rigorous Hilbert space justification for using linear splines.
  • Boundary Conditions are Key: The exact shape of the kernel (and thus the behavior of the interpolant) is dictated by the boundary terms in the inner product. They show how different boundary conditions lead to famous kernels like the Brownian motion kernel ($min\{x, y\}$) or the Brownian bridge.
  • Integration is Interpolation: They demonstrate that the trapezoidal rule for numerical integration is simply the result of integrating a kernel interpolant. This unifies interpolation and quadrature under one "kernel" roof.
  • Superconvergence as a Bridge: Usually, kernel error bounds are limited by the "native space" of the kernel. Superconvergence theory allows the authors to "reach up" and prove that if the function is twice-differentiable, the error drops at a rate of $O(h^2)$, even though the kernel itself only has one derivative.

Key Results

  • Explicit Kernel Formula: The paper provides a general formula for a family of piecewise linear kernels (Equation 3) that covers various boundary conditions.
  • Unified Error Rates: They prove that for a function $u \in W_2^\theta(0, 1)$, the $L_2$ error of the interpolant $P_n u$ satisfies: $$\|u - P_n u\|_{L_2} \leq C h^\theta \|u\|_{H_\theta}$$ for $\theta \in [1, 2]$. This perfectly matches classical spline theory results but arrives there using modern kernel machinery.

  • Green's Function Identity: They successfully identify the specific second-order ODE boundary value problem for which their piecewise linear kernel is the Green's function.

Limitations and Future Work

  • Dimensionality: The study is strictly 1D, focusing on the unit interval $[0, 1]$. Extending this to higher dimensions (where "piecewise linear" usually implies a mesh of simplices) is a significant next step.
  • Boundary Sensitivity: The superconvergence results for $\theta > 1.5$ require the target function to satisfy specific boundary conditions related to the ODE. If these aren't met, the "optimal" rates might not be achieved.
  • Higher-Order Splines: While this paper tackles linear splines, the methodology suggests that higher-order splines (cubic, etc.) could be treated similarly by looking at higher-order Sobolev spaces and their corresponding Green kernels.

Summary updated

Abstract

We consider piecewise linear interpolation from the perspective of kernel interpolation and quadrature. If the Sobolev space $W_2^1(0, 1)$ is equipped with a suitable inner product, its reproducing kernel is piecewise linear and gives rise to piecewise linear interpolation. We show that such kernels are Green kernels for certain second-order partial differential equations and use kernel-based superconvergence theory to obtain rates of convergence for approximation of functions lying in $W_2^s(0, 1)$ for $s \in [1, 2]$. The rates coincide with classical rates for linear splines.
BibTeX
@misc{karvonen2026piecewise,
  author = {Toni Karvonen and Gabriele Santin and Tizian Wenzel},
  title = {{Piecewise linear interpolation via kernels}},
  year = {2026},
  eprint = {2603.01555},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.01555},
}
Figure