Explicit RKHSs for Linear and Polynomial Kernels

Why the Monomial Scaling Matters

A polynomial kernel can look simple as a function of two inputs, yet its associated RKHS norm is not generally the sum of the squares of the ordinary polynomial coefficients. The kernel expansion assigns a scale to each feature; that scale determines how expensive the corresponding coefficient is in the RKHS norm. Understanding that relationship makes it possible to calculate norms explicitly and to see which polynomial functions a kernel permits.

We work on an input domain \(D\subseteq\mathbb R^p\). For a finite feature map \(\phi:D\to\mathbb R^m\), the kernel is \(k(x,z)=\phi(x)^\top\phi(z)\). The feature coordinates may be scaled versions of monomials. If these coordinates are linearly independent as functions on \(D\), each function in the associated RKHS has a unique feature-coordinate representation. If they are dependent, a function can have multiple representations, and its RKHS norm is determined by the least costly one.

Finite Feature Maps and Their Norms

The basic calculation can be stated for any finite feature map. Its importance here is that a polynomial kernel supplies a particular choice of feature coordinates, including their scaling.

Proof. The map \(w\mapsto f_w\) is injective on \(S\). In fact, if \(w\in S\) and \(w^\top\phi(x)=0\) for all \(x\in D\), then \(w\) is orthogonal to every vector spanning \(S\), so \(w\in S^\perp\). Thus \(w=0\). We can therefore define an inner product on these functions by \(\langle f_w,f_v\rangle_{\mathcal H}=w^\top v\) for \(w,v\in S\). This space is finite-dimensional and hence complete. For each \(z\in D\), the function \(k(\,\cdot\,,z)\) is \(f_{\phi(z)}\), since \(k(x,z)=\phi(x)^\top\phi(z)\); and \[ \langle f_w,k(\,\cdot\,,z)\rangle_{\mathcal H} =w^\top\phi(z)=f_w(z). \] So this is a Hilbert space of functions with reproducing kernel \(k\). If \(a\) is any coefficient vector representing \(f\), its orthogonal projection onto \(S\) represents the same function: \(a-\operatorname{proj}_S(a)\) is orthogonal to every \(\phi(x)\). The projection has no larger Euclidean norm, with equality only when \(a\in S\). Hence the unique representing vector in \(S\) has the smallest norm among all representations, proving the minimum formula. \(\square\)

For a linear kernel \(k(x,z)=x^\top z\), take \(\phi(x)=x\). Its functions are linear predictors \(f(x)=w^\top x\). When \(D\) spans \(\mathbb R^p\), the representation is unique and \(\|f\|_{\mathcal H}^2=\sum_{j=1}^p w_j^2\). If \(D\) lies in a proper subspace, different vectors \(w\) can agree on \(D\); the theorem says to use the shortest such vector.

Polynomial Kernels as Scaled Monomial Features

For \(x,z\in\mathbb R^p\), let \(d\ge 1\) be an integer. The homogeneous polynomial kernel \((x^\top z)^d\) contains monomials of exactly degree \(d\). By contrast, the inhomogeneous kernel \((c+x^\top z)^d\), with \(c>0\), includes monomials of every degree from zero through \(d\). The multinomial theorem gives the scales of all these features.

Proof. Apply the multinomial expansion to the \(p+1\) terms \(c,x_1z_1,\ldots,x_pz_p\). Choose nonnegative integers \(\alpha_1,\ldots,\alpha_p\) for the powers of the \(p\) input-coordinate terms; the remaining power of \(c\) is \(d-|\alpha|\). The corresponding coefficient is \(d!/((d-|\alpha|)!\alpha!)\), giving the displayed expansion. Each \(q_\alpha\) is positive because \(c>0\), so the coordinates \(\sqrt{q_\alpha}x^\alpha\) give a feature map for the kernel. For a polynomial with coefficients \(\beta_\alpha\), its feature-coordinate coefficients must be \(a_\alpha=\beta_\alpha/\sqrt{q_\alpha}\), since \(\sum_\alpha a_\alpha\phi_\alpha(x)=\sum_\alpha\beta_\alpha x^\alpha\). When the monomials are independent, this representation is unique, and the finite-feature theorem gives squared norm \(\sum_\alpha a_\alpha^2=\sum_\alpha\beta_\alpha^2/q_\alpha\). When they are dependent, the same theorem takes the minimum over all feature-coordinate representations; expressing those coordinates as polynomial coefficients gives the stated minimum. \(\square\)

For \(c=0\), the expansion has only terms with \(|\alpha|=d\): \[ (x^\top z)^d=\sum_{|\alpha|=d}\frac{d!}{\alpha!}x^\alpha z^\alpha. \] Accordingly, on a domain where the degree-\(d\) monomials are independent, the RKHS contains homogeneous polynomials of degree \(d\), with squared norm \(\sum_{|\alpha|=d}(\alpha!/d!)\beta_\alpha^2\). It does not automatically contain lower-degree terms or a constant term. The offset \(c>0\) is what supplies the lower-degree features in the inhomogeneous kernel.

When Feature Coordinates Are Not Unique

A formula that treats polynomial coefficients as unique must be used with care if the input domain is restricted. For example, on a line in \(\mathbb R^2\), the coordinate functions \(x_1\) and \(x_2\) may coincide or be proportional. The kernel still defines a norm on functions on that domain, but it is the minimum feature norm among representations, not the norm of an arbitrary coefficient vector.

Common Mistakes and Practical Meaning

• Using ordinary polynomial coefficients as feature coordinates. A feature \(\sqrt{q_\alpha}x^\alpha\) requires coordinate coefficient \(\beta_\alpha/\sqrt{q_\alpha}\). The norm contribution is \(\beta_\alpha^2/q_\alpha\), not \(\beta_\alpha^2\).
• Forgetting the distinction between homogeneous and inhomogeneous kernels. The kernel \((x^\top z)^d\) contains only degree-\(d\) monomials. Lower degrees appear in \((c+x^\top z)^d\) only when \(c>0\).
• Assuming coefficients are unique on every domain. A polynomial identity on all of \(\mathbb R^p\) has unique monomial coefficients, but restricting inputs can make features dependent. Use the minimum-norm representation in that case.
• Reading kernel scale as predictor scale. The RKHS norm measures feature-coordinate length. A larger monomial scaling in the feature map means a given polynomial coefficient requires a smaller feature-coordinate coefficient and can have a smaller norm.

These calculations give a concrete interpretation to regularization in a polynomial RKHS: the kernel’s expansion weights impose a particular quadratic penalty on polynomial coefficients. Changing the kernel’s degree, offset, or feature scaling changes both the functions available and the relative cost assigned to their monomial terms. That is why two kernels that both produce polynomial predictors need not define the same RKHS norm.