Interpolation with the Polynomial Kernels

A tour into interpolation with positive definite kernels

ATMA 2023 - Approximation: Theory, Methods and Applications,

Giacomo Elefantea, Wolfgang Erba, Francesco Marchettia, Emma Perracchioneb, Davide Poggialic, Gabriele Santind
aUniversita` di Padova , bPolitecnico di Torino, cFAR Networks S.r.l., dFondazione Bruno Kessler


The polynomial kernels are widely used in machine learning and they are one of the default choices to develop kernel-based classification and regression models. However, they are rarely used and considered in numerical analysis due to their lack of strict positive definiteness. In particular they do not enjoy the usual property of unisolvency for arbitrary point sets, which is one of the key properties used to build kernel-based interpolation methods. This work is devoted to establish some initial results for the study of these kernels, and their related interpolation algorithms, in the context of approximation theory. We will first prove necessary and sufficient conditions on point sets which guarantee the existence and uniqueness of an interpolant. We will then study the Reproducing Kernel Hilbert Spaces (or native spaces) of these kernels and their norms, and provide inclusion relations between spaces corresponding to different kernel parameters. With these spaces at hand, it will be further possible to derive generic error estimates which apply to sufficiently smooth functions, thus escaping the native space. Finally, we will show how to employ an efficient stable algorithm to these kernels to obtain accurate interpolants, and we will test them in some numerical experiments.

The polynomial kernels

The polynomial kernels are a family of kernels defined for \( x,y\in\mathbb{R}^d \) by

\( k_{a,p}(x, y) = \left(a + \langle x, y \rangle\right)^p,\;\;p\in\mathbb{N}, \; a\geq 0. \)

Polynomial Expansion I

For \(a\geq 0\) define

\[I_a(p, d):= \begin{cases} \left\{\zeta \in \mathbb{N}_0^{d}, |\zeta|\leq p\right\}, & a>0\\ \left\{\zeta \in \mathbb{N}_0^{d}, |\zeta|= p\right\}, & a=0, \end{cases} \]


\[M_a:= \begin{cases} M_{p}^d=\dim(\mathbb{P}_{p}^d), & a>0\\ M_{p}^{d-1}=\dim(\mathbb{H}_{p}^d), & a=0, \end{cases} \]


\( k_{a,p}(x, y) =\sum_{\zeta \in I_a(p,d)} d_\zeta^a x^\zeta y^\zeta. \)

where \[ d_\zeta^a:= \begin{cases} \frac{p! a^{p-|\zeta|}}{(p-|\zeta|)!\zeta!}, & a>0\\ \frac{p!}{\zeta!}, & a=0, \end{cases},\;\; \zeta \in I_a(p,d). \]

Polynomial Expansion II


Let \[ V:= \begin{bmatrix} x_1^{\zeta^{(1)}}&\dots & x_1^{\zeta^{({M_a})}}\\ \vdots & \ddots &\vdots\\ x_N^{\zeta^{(1)}}&\dots & x_N^{\zeta^{({M_a})}}\\ \end{bmatrix}. \]

Then for all \(a>0\) the kernel matrix satisfies

\[ A_{a,p}(X_N) := \left(k_{a,p}(x_i,x_j)\right)_{i,j=1}^N = V D V^T, \] where \[D:=diag\left(d^a_{\zeta^{(1)}}, \dots, d^a_{\zeta^{(M_a)}}\right)\]



The native space

The native space \(\mathcal{H}_{a, p}(\Omega)\) of \(k_{a,p}\) on \(\Omega\):

We have \[ \mathcal{H}_{a, p}(\Omega)= \begin{cases} \mathbb{P}_p^d(\Omega), & a>0,\\ \mathbb{H}_p^d(\Omega), & a=0, \end{cases} \] with \[ \left\langle f, g\right\rangle_{\mathcal{H}_{a,p}}:=\sum_{\gamma\in I_a(p, d)} \frac{1}{w_\gamma^a} D^\gamma f(0) D^\gamma g(0). \]


\[ w_\zeta^a:= (\zeta!)^2 d_\zeta^a= \begin{cases} \frac{p! \zeta!}{(p-|\zeta|)!} a^{p-|\zeta|}, & a>0,\\ p! \zeta!, & a=0.\\ \end{cases} \]

Inclusion relations

For any \(a\geq 0\), \(p\in\mathbb{N}\):


Let \(a\geq 0\), \(p\in\mathbb{N}\), and \(X\) be \(\mathcal{H}_{a,p}\)-unisolvent.
If \(X\subset X_{M_a}\subset B\subset\mathbb{R}^d\) is \(\mathbb{P}_p^d\)-unisolvent, then for \(f\in C(B)\) \[ \|I_{X,a,p} f\|_{\infty,\Omega} \leq \Lambda_{X_{M_a},p,B}^{pol} \|f\|_{\infty,B}, \] where \( \Lambda_{X_{M_a},p,B}^{pol} \) is the Lebesgue constant for polynomial interpolation of degree \(p\) on \(X_{M_a},B\).

Error estimation

Power function \[ P_{X,a,p}(x) :=\sup\limits_{0\neq f\in \mathcal{H}_{a, p}}\frac{\left|f(x) - I_{X,a,p} f(x)\right|}{\|f\|_{\mathcal{H}_{a,p}}} \]

Let \(X_N\subset\Omega\) be \(\mathcal{H}_{a,p}\)-unisolvent.
For all \(f\in C(\Omega)\) and \(x\in\Omega\)
\[ \begin{align} &\\ &\left|(f-I_{X,a,p} f)(x)\right| \leq E_{pol}(x) + E_{ker}(x). \end{align} \]

Here \[ E_{pol}(x):=\left(1 + \lambda_{X,a,p}(x)\right)\left\|f-f_p^\star\right\|_{\infty,\Omega} \] and \[ E_{ker}(x) :=P_{X,a,p}(x) \left\|f^\star - I_{X,a,p} f_p^\star\right\|_{\mathcal{H}_{a,p}}, \] with \[ f_p^\star:=\inf\limits_{g\in \mathbb{P}_p^d(\Omega)}\|f-g\|_{\infty,\Omega}. \]

Stable computations

Stable computations with RBF-QR:

Stable computations: Lagrange basis

Lagrange functions for the polynomial kernel with \(p=25\) and \(a=10\), for \(N=15\) Chebyshev points (black dots), computed with the direct method (gray lines) and with RBF-QR (black lines).

Stable computations: Approximation

Maximal absolute interpolation error for the function \(f(x) = \cos(10 x)\) using \(N=5, \dots, 50\) Chebyshev points. For each figure, we test a polynomial interpolant (gray line), and kernel interpolants with various values of \(p\), and \(a=5\) (left column) and \(a=10\) (right column). The kernel interpolants are computed with the direct method (first row) and with RBF-QR (second row).

Lebesgue function

Lagrange functions (top) and Lebesgue function (bottom) for interpolation with a polynomial kernel \(k_{5, p}\) on \(N=5\) Chebyshev points and various values of \(p\).

Lebesgue function

Growth of the Lebesgue constant associated to \(N=5, \dots, 45\) equally spaced (left) and Chebyshev (right) points. We test kernel interpolants with various values of \(p\), and \(a=5\) (first row) and \(a=10\) (second row).

Future directions