Equivalent Kernels and Identical RKHSs

Why Kernel Equality and Function-Space Equality Differ

A positive semidefinite kernel determines both a set of functions and a Hilbert-space norm on that set. These are separate pieces of information. Two kernels can generate exactly the same functions while assigning different lengths to those functions; conversely, a comparison of kernels can give precise bounds on how the two norms differ.

This distinction matters whenever a method uses an RKHS norm to measure complexity. The function set says which functions are available, while the norm determines how they are measured. We will compare kernels on the same input domain and make both parts of this distinction precise.

Definition: A kernel \(K\) on a set \(\mathcal X\) is positive semidefinite if it is symmetric and, for every finite list \(x_1,\ldots,x_m\in\mathcal X\) and coefficients \(a_1,\ldots,a_m\in\mathbb R\), \(\sum_{i,j=1}^m a_i a_j K(x_i,x_j)\geq 0\). Its reproducing kernel Hilbert space is denoted \(\mathcal H_K\); its inner product and norm are \(\langle\cdot,\cdot\rangle_K\) and \(\|\cdot\|_K\). The reproducing property is \(f(x)=\langle f,K(\cdot,x)\rangle_K\).

We say two RKHSs on the same domain have the same function set when \(\mathcal H_{K_1}=\mathcal H_{K_2}\) as sets of pointwise-defined functions. They have the same norm when this set is the same and \(\|f\|_{K_1}=\|f\|_{K_2}\) for every function in it. The latter is stronger: it also implies that the inner products agree, by the polarization identity.

Scaling a Kernel

The simplest way to change a kernel without changing its function set is to multiply it by a positive constant. The norm changes in the opposite direction to the kernel scale.

Theorem: Let \(K\) be a positive semidefinite kernel and let \(c>0\). Then \(\mathcal H_{cK}=\mathcal H_K\) as sets, and for every \(f\) in this common set, \[ \|f\|_{cK}^2=\frac{1}{c}\|f\|_K^2. \]

To verify the claim, first note that \(cK\) is positive semidefinite because every quadratic form for \(cK\) is \(c\) times the corresponding nonnegative quadratic form for \(K\). On the vector space \(\mathcal H_K\), define a new inner product by \(\langle f,g\rangle_{cK}=c^{-1}\langle f,g\rangle_K\). This is a Hilbert-space inner product: rescaling a complete norm by a positive constant preserves completeness. Its evaluation property is \[ \langle f,(cK)(\cdot,x)\rangle_{cK} =\langle f,cK(\cdot,x)\rangle_K =\langle f,K(\cdot,x)\rangle_K =f(x). \] Thus this Hilbert space has reproducing kernel \(cK\). By uniqueness of the RKHS associated with a kernel, it is \(\mathcal H_{cK}\), with the stated norm. \(\square\)

Worked Example: Scaling an Affine-Function Kernel

On \(\mathbb R\), consider \(K(x,z)=1+xz\). Its feature representation is \(K(x,z)=(1,x)^\mathsf T(1,z)\), so its RKHS consists of affine functions \(f(x)=a+bx\), with \(\|f\|_K^2=a^2+b^2\). Now take \(\widetilde K=4K\).

The scaling result gives the same affine functions and \[ \|a+bx\|_{\widetilde K}^2=\frac{a^2+b^2}{4}. \] For example, \(f(x)=2+3x\) has squared norm \(2^2+3^2=13\) under \(K\), and squared norm \(13/4\) under \(\widetilde K\). The function set is unchanged, but the norms are not equal.

For a nonzero kernel, multiplying by \(c\neq 1\) therefore does not preserve the norm. Indeed, the kernel itself is determined by its RKHS inner product: \(K(x,z)=\langle K(\cdot,z),K(\cdot,x)\rangle_K\). Equal inner products on an identical function set consequently imply identical kernels.

Kernel Order and RKHS Inclusion

A useful comparison between two kernels is defined by their finite quadratic forms. This comparison gives an exact test for continuous inclusion of their RKHSs, including a bound on the norm of that inclusion.

Definition: For positive semidefinite kernels \(K_1,K_2\) on \(\mathcal X\), write \(K_1\preceq K_2\) if, for every finite list \(x_1,\ldots,x_m\) and every \(a_1,\ldots,a_m\), \[ \sum_{i,j=1}^m a_i a_j K_1(x_i,x_j) \leq \sum_{i,j=1}^m a_i a_j K_2(x_i,x_j). \]

The inclusion result rests on a characterization of the RKHS norm using finite evaluations. For any function \(f:\mathcal X\to\mathbb R\), membership in \(\mathcal H_K\) is equivalent to the existence of a finite constant \(B\) such that \[ \left|\sum_{i=1}^m a_i f(x_i)\right|^2 \leq B\sum_{i,j=1}^m a_i a_j K(x_i,x_j) \] for every finite list and coefficients, with the left side required to be zero whenever the quadratic form on the right is zero. The smallest such \(B\) is \(\|f\|_K^2\).

To see this, consider the linear span of the sections \(K(\cdot,x)\) in \(\mathcal H_K\). A finite combination \(g=\sum_i a_iK(\cdot,x_i)\) has squared norm \(\sum_{i,j}a_i a_jK(x_i,x_j)\), and \(\langle f,g\rangle_K=\sum_i a_i f(x_i)\) when \(f\in\mathcal H_K\). The displayed inequality is precisely the condition that this linear functional on the span is well-defined and bounded. If it is bounded, it extends to the closure of the span, which is all of \(\mathcal H_K\); the Riesz representation theorem supplies a function \(h\in\mathcal H_K\) representing it. Taking \(g=K(\cdot,x)\) gives \(h(x)=f(x)\). The norm of the functional is \(\|h\|_K\), proving the characterization.

Theorem: For positive semidefinite kernels \(K_1,K_2\) on the same domain and a finite constant \(C\geq 0\), \[ K_1\preceq C K_2 \quad\Longleftrightarrow\quad \mathcal H_{K_1}\subseteq\mathcal H_{K_2} \ \text{and}\ \|f\|_{K_2}\leq \sqrt C\,\|f\|_{K_1} \quad\text{for every }f\in\mathcal H_{K_1}. \]

Proof. Suppose first that \(K_1\preceq CK_2\). For \(f\in\mathcal H_{K_1}\), the finite-evaluation characterization gives \[ \left|\sum_i a_i f(x_i)\right|^2 \leq \|f\|_{K_1}^2\sum_{i,j}a_i a_jK_1(x_i,x_j) \leq C\|f\|_{K_1}^2\sum_{i,j}a_i a_jK_2(x_i,x_j). \] The characterization for \(K_2\) now shows that \(f\in\mathcal H_{K_2}\) and \(\|f\|_{K_2}^2\leq C\|f\|_{K_1}^2\).

For the converse, let \(J:\mathcal H_{K_1}\to\mathcal H_{K_2}\) be the inclusion. The assumed norm bound makes \(J\) bounded with operator norm at most \(\sqrt C\). Its adjoint satisfies \(J^*K_2(\cdot,x)=K_1(\cdot,x)\), since for every \(f\in\mathcal H_{K_1}\), \[ \langle f,J^*K_2(\cdot,x)\rangle_{K_1} =\langle Jf,K_2(\cdot,x)\rangle_{K_2} =f(x) =\langle f,K_1(\cdot,x)\rangle_{K_1}. \] Therefore, for any finite list and coefficients, \[ \left\|\sum_i a_iK_1(\cdot,x_i)\right\|_{K_1} =\left\|J^*\sum_i a_iK_2(\cdot,x_i)\right\|_{K_1} \leq \sqrt C\left\|\sum_i a_iK_2(\cdot,x_i)\right\|_{K_2}. \] Squaring gives \(K_1\preceq CK_2\). \(\square\)

Worked Example: Two Norms on the Same Finite-Domain Function Set

Let \(\mathcal X=\{u,v\}\), with kernels represented in the order \(u,v\) by \[ K_1=\begin{pmatrix}1&0\\0&4\end{pmatrix}, \qquad K_2=\begin{pmatrix}4&0\\0&1\end{pmatrix}. \] Both matrices are positive definite. For either diagonal kernel with diagonal entries \(\lambda_u,\lambda_v\), every function \(f\) on the two-point domain belongs to the RKHS and has squared norm \(f(u)^2/\lambda_u+f(v)^2/\lambda_v\). Thus \[ \|f\|_{K_1}^2=f(u)^2+\frac{f(v)^2}{4}, \qquad \|f\|_{K_2}^2=\frac{f(u)^2}{4}+f(v)^2. \]

Each coefficient in either squared norm is at most four times its counterpart in the other, so \[ \frac14\|f\|_{K_1}^2\leq\|f\|_{K_2}^2\leq4\|f\|_{K_1}^2. \] The bounds are sharp: use the function with values \((1,0)\) for the left equality and \((0,1)\) for the right equality. Hence the function sets agree and the norms are equivalent, but the norms are not equal.

Equivalent Norms and Identical Function Sets

Two norms on a common vector space are equivalent if there are constants \(0<m\leq M<\infty\) such that \(m\|f\|_{K_1}\leq\|f\|_{K_2}\leq M\|f\|_{K_1}\) for every \(f\). For RKHSs on the same domain, identical function sets always have equivalent norms. The evaluation maps are continuous in each RKHS, and that pointwise control is what makes the conclusion possible.

For completeness, consider the identity map \(I:\mathcal H_{K_1}\to\mathcal H_{K_2}\) when the function sets agree. If \(f_n\to f\) in \(\mathcal H_{K_1}\), continuity of each evaluation implies \(f_n(x)\to f(x)\) for every \(x\). If also \(If_n\to g\) in \(\mathcal H_{K_2}\), continuity there implies \(f_n(x)\to g(x)\) for every \(x\). Hence \(f(x)=g(x)\) for all \(x\), so the graph of \(I\) is closed. Both RKHSs are complete, so the closed graph theorem implies \(I\) is bounded. Reversing the roles of the two spaces proves the reverse bound. Thus there are constants \(m,M>0\) with \[ m\|f\|_{K_1}\leq\|f\|_{K_2}\leq M\|f\|_{K_1}. \]

Corollary: Two RKHSs on the same domain have the same function set if and only if their kernels satisfy two-sided comparisons \(K_1\preceq C K_2\) and \(K_2\preceq D K_1\) for some finite positive constants \(C,D\). Such comparisons are equivalent to equivalence of their norms. The norms are equal, a stronger condition, exactly when the kernels are equal.

Indeed, the two kernel inequalities give inclusions in both directions by the theorem. Conversely, equal function sets give bounded identity maps in both directions by the closed graph argument, and the reverse implication in the theorem converts those bounds into the two kernel inequalities. If the norms are equal, the reproducing property gives equal inner products, and the kernel is recovered from the inner products of its sections; therefore the kernels coincide. Equal kernels, in turn, define the same RKHS norm by uniqueness.

Worked Example: One-Way Kernel Comparison and Strict Inclusion

On \(\mathcal X=\mathbb N\), set \(K_1(i,j)=\mathbf 1\{i=j\}\) and \(K_2(i,j)=i^2\mathbf 1\{i=j\}\). Both are positive semidefinite, and \(K_1\preceq K_2\), since for any finite coefficients their quadratic forms are \(\sum_i a_i^2\) and \(\sum_i i^2a_i^2\), respectively.

For a diagonal kernel with positive diagonal values \(\lambda_i\), the RKHS consists of functions satisfying \(\sum_i f(i)^2/\lambda_i<\infty\), with that sum as the squared norm. Consequently, \(\mathcal H_{K_1}\) is the square-summable sequences, while \(\mathcal H_{K_2}\) consists of sequences with \(\sum_i f(i)^2/i^2<\infty\). The theorem gives \(\|f\|_{K_2}\leq\|f\|_{K_1}\) on \(\mathcal H_{K_1}\).

To verify that the inclusion is strict, take \(f(i)=1/\sqrt i\). Then \[ \sum_{i=1}^\infty f(i)^2=\sum_{i=1}^\infty\frac1i=\infty, \qquad \sum_{i=1}^\infty\frac{f(i)^2}{i^2} =\sum_{i=1}^\infty\frac1{i^3}<\infty. \] Thus \(f\in\mathcal H_{K_2}\) but \(f\notin\mathcal H_{K_1}\). One-way kernel domination gives inclusion, not equality of function sets.

Common Pitfall and Practical Interpretation

A common mistake is to infer that two kernels with the same RKHS functions must have the same kernel, or the same norm. That conclusion confuses the set with its geometry. For example, \(K\) and \(4K\) have the same functions, but their squared norms differ by a factor of four. The correct conclusion is that their norms are equivalent, not necessarily equal.

The kernel-order criterion is useful because it separates these questions. A one-sided inequality gives a continuous inclusion and a norm bound. Two-sided inequalities give the same function set with equivalent norms. Exact equality of norms requires the stronger condition \(K_1=K_2\). When comparing two proposed kernels, check the finite quadratic forms first, then interpret the resulting inclusions and bounds.

Check Your Understanding

Use the definitions and results above to answer the following questions.

If \(\widetilde K=9K\), what is the relationship between \(\mathcal H_{\widetilde K}\) and \(\mathcal H_K\), and how do their norms compare?
What does \(K_1\preceq 4K_2\) imply about RKHS inclusion and the two norms?
Why do two RKHSs on the same domain with identical function sets have equivalent norms?
Can \(K_1\preceq K_2\) alone establish that the two RKHS function sets are equal? Explain.
What additional condition, beyond having the same function set, ensures that two RKHS norms are exactly equal?