Interpolation with the Polynomial Kernels

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 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. \)

• They are positive definite (p.d.)
• They are not strictly p.d.: There exist sets of points which makes the kernel matrix singular.

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} \]

Then

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

• \(p\in\mathbb{N}\) and \(a\geq 0\)
• \(\left\{\zeta^{(i)}\right\}_{i=1}^{M_a}\) an enumeration of \(I_a(p, d)\)
• \(X_N\subset\Omega\) a set of \(N\leq M_a\) pairwise distinct points.

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

• The kernel matrix \(A_{a,p}(X_N)\) is invertible if and only if there exists \(X_N\subset X_{M_a}\) which is \(\mathbb{P}_p^d(\Omega)\)-unisolvent if \(a>0\), or \(\mathbb{H}_p^d(\Omega)\)-unisolvent if \(a=0\).
• If \(N=M_a\) and \(X_N\) are \(\mathbb{P}_p^d\)-unisolvent (if \(a>0\)) or \(\mathbb{H}_p^d\)-unisolvent (if \(a=0\)), then the polynomial kernel interpolant coincides with the polynomial interpolant from the corresponding space.

Let \(a> 0\) and \(X_N\subset\Omega\) pairwise distinct.
For any \(p\geq d (N-1)\) there exists a set \(X_{M_p^d}\subset \Omega\) of \(M_p^d\) points such that \(X_N\subset X_{M_p^d}\) and \(X_{M_p^d}\) is \(\mathbb{P}_p^d\)-unisolvent.

\[\Downarrow\]

\(A_{a,p}(X_N)\) is invertible if \(p\geq d (N-1)\).

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

• \(k_{a,p}(\cdot, x) \in \Omega\) for all \(x\in\Omega\)
• \(\left\langle k_{a,p}(\cdot, x), f\right\rangle_{\mathcal{H}_{a, p}} = f(x)\), \(x\in\Omega\), \(f\in\mathcal{H}_{a, p}\).

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} \]

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

• If \(0 < a' \leq a \) then \(\mathcal{H}_{a, p}=\mathcal{H}_{a', p}\) as sets and

  \[ \left(\frac{a'}{a}\right)^{p/2} \left\|f\right\|_{\mathcal{H}_{a', p}} \leq \left\|f\right\|_{\mathcal{H}_{a, p}} \leq \left\|f\right\|_{\mathcal{H}_{a', p}}. \]

• If \( a > 0\) then \(\mathcal{H}_{0,p}\subset \mathcal{H}_{a, p}\) with same norm for \(f\in \mathcal{H}_{0, p}\).
• If \(a>0\) and \(p,q\in\mathbb{N}\) with \(0\leq q\leq p\), then \(\mathcal{H}_{a, q}\subset\mathcal{H}_{a, p}\) with \(d_p:=p-q\) and \[ a^{\frac{d_p}{2}} \left\|f\right\|_{\mathcal{H}_{a, p}} \leq \left\|f\right\|_{\mathcal{H}_{a, q}} \leq a^\frac{d_p}{2} \binom{p}{d_p}^\frac{1}{2} \left\|f\right\|_{\mathcal{H}_{a, p}}. \]

• Lagrange basis \(\left\{\ell_{i,a,p}\right\}_{i=1}^N\) of \(V_{a,p}(X_N)=\mathrm{span}\{k_{a,p}(\cdot, x):x\in X_N\}\),
• Lebesgue function \[ \lambda_{X_N,a,p}(x):=\sum_{i=1}^N \left|\ell_{i,a,p}(x)\right|, \]
• Lebesgue constant \[\Lambda_{X,a,p,\Omega}:=\max_{x\in\Omega}\lambda_{X,a,p}(x)\]

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\).

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} \]

• \(V=Q R\)
• \(Q\in\mathbb{R}^{N\times N}\)
• \(R:=[R_1|R_2]\), \(R_1\in \mathbb{R}^{N\times N}\),
• \(D=\begin{bmatrix}D_1 &0 \\ 0 &D_2\end{bmatrix}\), \(D_1\in \mathbb{R}^{N\times N}\)

Then

\[ A_{a,p}(X_N) = V \begin{bmatrix}I \\ D_2 R_2^T R_1^{-T} D_1^{-1}\end{bmatrix} D_1 R_1^T Q^T \]

New basis \[V':= V \begin{bmatrix}I \\ D_2 R_2^T R_1^{-T} D_1^{-1}\end{bmatrix} \]