Sums, Products, and Pullbacks of Kernels

How Kernel Operations Build New Function Spaces

A kernel can be modified without losing positive definiteness, and each such modification has a useful feature-space interpretation. Adding kernels combines two sources of similarity; multiplying them requires agreement in both feature representations; composing a kernel with an input map transfers it to a new domain. These constructions also describe what functions the resulting RKHS contains and how their norms are determined.

Throughout, let $X$ be a nonempty set. A real-valued kernel $k$ on $X$ is positive definite if it is symmetric and, for every finite collection $x_1,\ldots,x_n\in X$ and real coefficients $c_1,\ldots,c_n$, $\sum_{i,j=1}^n c_i c_j k(x_i,x_j)\geq 0$. Equivalently, every finite Gram matrix $[k(x_i,x_j)]_{i,j=1}^n$ is positive semidefinite. We use the RKHS feature-map characterization: if $\phi:X\to H$ takes values in a Hilbert space and $k(x,x')=\langle\phi(x),\phi(x')\rangle_H$, then $k$ is positive definite. The associated RKHS can be represented using the closed span of the feature vectors, with functions $x\mapsto\langle w,\phi(x)\rangle_H$ and the smallest feature-space norm among vectors representing each function.

Sums: Combine Features, Minimize Over Decompositions

Let $k_1$ and $k_2$ be positive definite kernels on the same set $X$, with RKHSs $H_1$ and $H_2$. Write $\phi_1(x)=k_1(\cdot,x)\in H_1$ and $\phi_2(x)=k_2(\cdot,x)\in H_2$ for their canonical feature maps. The feature map for the sum is the pair of features in the Hilbert direct sum.

Theorem: The kernel $k_+(x,x')=k_1(x,x')+k_2(x,x')$ is positive definite. Its RKHS consists of functions $f=f_1+f_2$, with $f_1\in H_1$ and $f_2\in H_2$, and its norm is $$ \|f\|_{H_+}^2 = \inf_{\substack{f=f_1+f_2\\ f_1\in H_1,\ f_2\in H_2}} \left(\|f_1\|_{H_1}^2+\|f_2\|_{H_2}^2\right). $$

Proof. In $H_1\oplus H_2$, define $\phi_+(x)=(\phi_1(x),\phi_2(x))$. Then $\langle\phi_+(x),\phi_+(x')\rangle=k_1(x,x')+k_2(x,x')$, so the feature-map characterization proves positive definiteness. Define $A:H_1\oplus H_2\to\mathbb R^X$ by $A(f_1,f_2)=f_1+f_2$. Its null space is closed: it is the intersection, over $x\in X$, of the kernels of the continuous maps $(f_1,f_2)\mapsto f_1(x)+f_2(x)$. Thus the image functions have the quotient norm $\inf_{A(f_1,f_2)=f}(\|f_1\|^2+\|f_2\|^2)^{1/2}$, with the infimum attained by the representative orthogonal to the null space. The evaluation feature of this quotient at $x$ is the class of $(\phi_1(x),\phi_2(x))$; its inner product with the evaluation feature at $x'$ is $k_+(x,x')$. The quotient is therefore the RKHS of $k_+$, giving the stated norm. $\square$

Worked Example: A Sum Kernel Gives Affine Functions

On $X=\mathbb R$, take $k_1(x,x')=xx'$ and $k_2(x,x')=1$. The first kernel has feature $x$ and RKHS consisting of $f_1(x)=ax$ with norm $|a|$; the second has feature $1$ and RKHS consisting of constants $f_2(x)=b$ with norm $|b|$.

The sum kernel is $k_+(x,x')=xx'+1$. Every affine function $f(x)=ax+b$ is the sum of $ax$ and $b$. This representation is unique: if $ax+b=\tilde a x+\tilde b$ for every real $x$, evaluating at $x=0$ gives $b=\tilde b$, and evaluating at $x=1$ then gives $a=\tilde a$. Consequently, the minimum in the sum norm formula is $a^2+b^2$, and $\|f\|_{H_+}^2=a^2+b^2$. The feature $(x,1)$ gives the same kernel directly.

Products: Tensor Features and Products of Functions

For kernels on the same input set, the product feature lives in the tensor product of the original feature spaces. The inner product of two simple tensors satisfies $\langle u_1\otimes u_2,v_1\otimes v_2\rangle=\langle u_1,v_1\rangle\langle u_2,v_2\rangle$, which is exactly the multiplication rule needed for kernels.

Theorem: If $k_1,k_2$ are positive definite with feature maps $\phi_1,\phi_2$, then $k_\times(x,x')=k_1(x,x')k_2(x,x')$ is positive definite, with feature map $\phi_\times(x)=\phi_1(x)\otimes\phi_2(x)$. Moreover, for $f_i\in H_i$, the pointwise product $f_1f_2$ belongs to the RKHS $H_\times$ of $k_\times$, and $$ \|f_1f_2\|_{H_\times}\leq \|f_1\|_{H_1}\|f_2\|_{H_2}. $$

Proof. The tensor feature satisfies $\langle\phi_\times(x),\phi_\times(x')\rangle=k_1(x,x')k_2(x,x')$, proving positive definiteness. Represent $f_i(x)=\langle w_i,\phi_i(x)\rangle$ using vectors in the corresponding feature spans, with $\|w_i\|=\|f_i\|_{H_i}$. Then \[ f_1(x)f_2(x) = \langle w_1\otimes w_2,\phi_1(x)\otimes\phi_2(x)\rangle. \] Project $w_1\otimes w_2$ orthogonally onto the closed span of the product features. This does not change any of these inner products, and cannot increase its norm. The RKHS norm of the represented function is at most the norm of the projected vector, which is at most $\|w_1\otimes w_2\|=\|w_1\|\|w_2\|$. This proves the claim. $\square$

For a finite Gram matrix, this argument also proves the Schur product theorem: the entrywise product of two positive semidefinite Gram matrices is positive semidefinite. Factor each matrix as a Gram matrix of vectors; the entrywise product is the Gram matrix of the pairwise tensor products of those vectors.

Worked Example: A Product Kernel Gives Quadratic Polynomials

On $\mathbb R$, let both kernels be $k(x,x')=1+xx'$. Each has feature $(1,x)$ in $\mathbb R^2$. Their product is $k_\times(x,x')=(1+xx')^2=1+2xx'+x^2x'^2$. The tensor feature in $\mathbb R^2\otimes\mathbb R^2$, using the coordinate order $(1,1),(1,x),(x,1),(x,x)$, is $(1,x,x,x^2)$.

A coefficient vector $(a,d,e,c)$ represents $a+(d+e)x+cx^2$, and its squared norm in this feature space is $a^2+d^2+e^2+c^2$. For a given $f(x)=a+bx+cx^2$, the constraint is $d+e=b$. The squared norm is minimized at $d=e=b/2$: indeed, $d^2+e^2=\tfrac12(d+e)^2+\tfrac12(d-e)^2\geq b^2/2$, with equality when $d=e$. Hence the product-kernel RKHS consists of all quadratic polynomials, and $\|f\|_{H_\times}^2=a^2+b^2/2+c^2$.

As a check, the canonical feature $(1,\sqrt{2}x,x^2)$ has inner product $1+2xx'+x^2x'^2$ at $x,x'$. A coefficient vector $(a,b/\sqrt{2},c)$ then represents $f$ and has squared norm $a^2+b^2/2+c^2$, as calculated above.

Pullbacks: Transfer a Kernel Along an Input Map

Let $T:X\to Z$ be any map, and let $k$ be a positive definite kernel on $Z$. The pullback kernel on $X$ is obtained by evaluating $k$ at the mapped inputs. No continuity, injectivity, or surjectivity assumption on $T$ is needed for positive definiteness.

Theorem: The kernel $k_T(x,x')=k(Tx,Tx')$ is positive definite. If $H$ is the RKHS of $k$, its associated RKHS on $X$ consists of the functions $g\circ T$, $g\in H$, with norm $$ \|f\|_{H_T} = \inf_{\substack{g\in H\\g\circ T=f}}\|g\|_H. $$

Proof. For any finite $x_1,\ldots,x_n\in X$, the matrix $[k_T(x_i,x_j)]$ is the Gram matrix of $k$ at $Tx_1,\ldots,Tx_n$, so it is positive semidefinite. For the function-space statement, define $A:H\to\mathbb R^X$ by $Ag=g\circ T$. Its null space $N=\{g\in H:g(Tx)=0\text{ for all }x\in X\}$ is closed, since each evaluation map on $H$ is continuous. The image is thus represented by the quotient Hilbert space $H/N$, whose norm is the infimum over representatives and is attained by the representative in $N^\perp$. The evaluation feature at $x$ is the class of $k(\cdot,Tx)$; inner products of these classes equal $k(Tx,Tx')$, because vectors in $N$ are orthogonal to every such kernel section. The quotient therefore has reproducing kernel $k_T$ and is its RKHS. $\square$

Worked Example: A Nonlinear Input Map

Take $Z=X=\mathbb R$, $k(s,t)=1+st$, and $T(u)=u^2$. The pullback is $k_T(u,v)=1+u^2v^2$, with feature $(1,u^2)$. The original RKHS contains affine functions $g(t)=a+bt$, with squared norm $a^2+b^2$, as established by the two-coordinate feature $(1,t)$.

Composing gives $g(T(u))=a+bu^2$, so the pullback space consists of functions $f(u)=a+bu^2$. These coefficients are unique: if $a+bu^2=\tilde a+\tilde b u^2$ for every $u$, setting $u=0$ gives $a=\tilde a$, and setting $u=1$ gives $b=\tilde b$. Thus the minimum norm over representations is $a^2+b^2$, and $\|f\|_{H_T}^2=a^2+b^2$. The map changes the inputs but does not turn the quadratic term into a linear function of $u$.

What These Constructions Do—and Do Not—Say

The feature constructions explain why the three operations preserve positive definiteness, while the norm formulas determine the cost of representing functions in the new RKHS. In practice, sums can combine different types of effects, products can encode interactions, and pullbacks can impose a chosen representation of the inputs. Those interpretations depend on the features and the resulting function spaces, not only on the algebraic form of the kernel.

A common mistake is to assume that the product-kernel RKHS consists only of products $f_1f_2$, or that the norm of such a product must equal the product of the two norms. The tensor construction guarantees that each such product belongs to the space and gives an upper bound on its norm. The full RKHS is generated by the closed span of product-kernel sections, so it can contain sums and limits of represented functions as well; its norm is the minimum feature norm, which can be strictly smaller than the norm of a particular tensor representation.

Likewise, a sum-kernel norm is not generally the square root of the sum of the norms of two arbitrarily chosen components. A function may have multiple decompositions $f=f_1+f_2$, and the RKHS norm uses the least possible squared component norm over all such decompositions. For a pullback, different functions on $Z$ may agree after composition with $T$, so the norm is the least norm among all such representatives. These minimum-norm conventions are essential whenever the feature representation is not unique.

Check Your Understanding

Use the feature constructions and norm interpretations to answer the following.

Why does putting two feature maps into a Hilbert direct sum produce the sum of their kernels?
What feature map represents the product of two kernels, and which inner-product identity verifies it?
For the quadratic $a+bx+cx^2$ in the product-kernel example, why do the two middle tensor coordinates share the coefficient $b$?
If $T$ is not injective, why might more than one function in the original RKHS represent the same pullback function?
Does the product-kernel theorem say that every function in its RKHS is one product $f_1f_2$? Explain.