Checking Whether a Similarity Formula Is a Kernel

Why Similarity Formulas Need a Test

A formula that assigns a number to each pair of inputs may look like a reasonable measure of similarity without being a kernel. In kernel methods, this distinction matters: a valid kernel gives a positive semidefinite Gram matrix for every finite collection of inputs. That condition is what lets the formula act like an inner product in a feature space. A single failed symmetry check or a single negative quadratic form rules out validity.

Let $\mathcal X$ be a nonempty input domain. For points $x_1,\ldots,x_m\in\mathcal X$, the Gram matrix of a real-valued function $k:\mathcal X\times\mathcal X\to\mathbb R$ has entries $K_{ij}=k(x_i,x_j)$. The same point may appear more than once in this list; the definition must hold for every finite list.

Definition: A real-valued function $k$ is a (positive semidefinite) kernel on $\mathcal X$ if it is symmetric, meaning $k(x,y)=k(y,x)$ for all $x,y\in\mathcal X$, and for every integer $m\geq 1$, every $x_1,\ldots,x_m\in\mathcal X$, and every $a_1,\ldots,a_m\in\mathbb R$, $$ \sum_{i=1}^{m}\sum_{j=1}^{m}a_i a_j k(x_i,x_j)\geq 0. $$ Equivalently, every finite Gram matrix is positive semidefinite.

The quadratic-form condition tests all coefficient vectors, not just vectors with nonnegative entries. For a symmetric Gram matrix $K$, it says $a^\mathsf{T}Ka\geq 0$ for every real vector $a$. A negative value for even one choice of points and coefficients is a conclusive counterexample. Conversely, a few successful tests are not a proof: the condition must hold for every finite list of inputs.

Three Direct Checks

When a formula is proposed, first check symmetry. If it passes, look for a small Gram matrix whose quadratic form is negative. A two-point example is often enough. Nonnegative diagonal entries are necessary, since choosing a list with one point gives $k(x,x)\geq 0$, but they do not guarantee positive semidefiniteness.

Worked Example: An Asymmetric Candidate

Consider $k(x,y)=x+2y$ on $\mathbb R$. A kernel must satisfy $k(x,y)=k(y,x)$ for every pair. At $x=0$ and $y=1$, $$ k(0,1)=0+2(1)=2,\qquad k(1,0)=1+2(0)=1. $$

The two values differ, so the formula is not symmetric and cannot be a kernel. There is no need to test a quadratic form once symmetry has failed.

Worked Example: A Symmetric Candidate With a Negative Quadratic Form

Consider $k(x,y)=1-xy$ on $\mathbb R$. It is symmetric, but symmetry alone does not suffice. Use the points $x_1=0$ and $x_2=1$. The Gram matrix is $$ K= \begin{pmatrix} k(0,0)&k(0,1)\\ k(1,0)&k(1,1) \end{pmatrix} = \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}. $$

For $a=(1,-1)^\mathsf{T}$, the quadratic form is $$ a^\mathsf{T}Ka = \begin{pmatrix}1&-1\end{pmatrix} \begin{pmatrix}1&1\\1&0\end{pmatrix} \begin{pmatrix}1\\-1\end{pmatrix} = \begin{pmatrix}1&-1\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix} =-1. $$

Since this is negative, the candidate is not a kernel, even though its diagonal values $k(x,x)=1-x^2$ happen to be nonnegative at some inputs.

The tests above are useful for rejecting a formula, but a formula that passes a few selected tests still needs a general argument. One direct way to prove validity is to represent the formula as an inner product.

Theorem (Feature-map criterion): If there is a real Hilbert space $\mathcal H$ and a map $\phi:\mathcal X\to\mathcal H$ such that $k(x,y)=\langle\phi(x),\phi(y)\rangle_{\mathcal H}$ for every $x,y$, then $k$ is a kernel.

Proof. The inner product is symmetric, so $k(x,y)=k(y,x)$. For any finite list of points and real coefficients, $$ \sum_{i=1}^{m}\sum_{j=1}^{m}a_i a_j k(x_i,x_j) = \sum_{i=1}^{m}\sum_{j=1}^{m}a_i a_j \langle\phi(x_i),\phi(x_j)\rangle_{\mathcal H} = \left\langle\sum_{i=1}^{m}a_i\phi(x_i),\sum_{j=1}^{m}a_j\phi(x_j)\right\rangle_{\mathcal H} = \left\|\sum_{i=1}^{m}a_i\phi(x_i)\right\|_{\mathcal H}^{2} \geq 0. $$ Thus every finite Gram matrix is positive semidefinite, and $k$ is a kernel. $\square$

Worked Example: Certifying a Linear Kernel With an Offset

On $\mathbb R$, consider $k(x,y)=1+xy$. Define $\phi(x)=(1,x)\in\mathbb R^2$. Then $$ \langle\phi(x),\phi(y)\rangle=1\cdot 1+xy=1+xy=k(x,y), $$ so the feature-map criterion proves this is a kernel.

For an explicit check, take the points $-1,0,2$. Their Gram matrix is $$ K= \begin{pmatrix} 2&1&-1\\ 1&1&1\\ -1&1&5 \end{pmatrix}. $$ For any $a=(a_1,a_2,a_3)^\mathsf{T}$, the feature representation gives $$ a^\mathsf{T}Ka=(a_1+a_2+a_3)^2+(-a_1+2a_3)^2\geq 0. $$ For example, $a=(1,-1,0)^\mathsf{T}$ gives $a^\mathsf{T}Ka=0^2+(-1)^2=1$. The general feature-map argument, rather than this one numerical check, establishes validity for every finite sample.

Feature Maps Are Also a Characterization

The feature-map criterion is not only a convenient sufficient condition. For a real symmetric function, the finite Gram-matrix condition also guarantees that some Hilbert-space feature map exists. This explains why the quadratic-form test captures the inner-product structure required of a kernel.

Theorem (Feature representation): A real-valued function $k$ on $\mathcal X\times\mathcal X$ is a kernel if and only if there are a real Hilbert space $\mathcal H$ and a map $\phi:\mathcal X\to\mathcal H$ such that $k(x,y)=\langle\phi(x),\phi(y)\rangle_{\mathcal H}$ for all $x,y\in\mathcal X$.

Proof of the converse. Assume $k$ is symmetric and satisfies the finite quadratic-form condition. Begin with the real vector space $V$ of finite formal sums $\sum_i a_i e_{x_i}$, where $e_x$ is a formal symbol for each $x\in\mathcal X$. Define a bilinear form by $$ \left\langle\sum_i a_i e_{x_i},\sum_j b_j e_{y_j}\right\rangle_0 = \sum_i\sum_j a_i b_j k(x_i,y_j). $$

Symmetry of $k$ makes this form symmetric. Its value on a vector paired with itself is nonnegative by the assumed finite quadratic-form condition. For a nonnegative symmetric bilinear form, every zero-length vector is orthogonal to every vector: if $\langle v,v\rangle_0=0$, then nonnegativity of $\langle v+t w,v+t w\rangle_0$ for every real $t$ forces $\langle v,w\rangle_0=0$. Otherwise a sufficiently small $t$ of the opposite sign would make the expression negative.

Consequently, the vectors of zero length form a subspace orthogonal to all of $V$. Quotient $V$ by that subspace. The bilinear form then defines an inner product on the quotient, and completing this inner-product space gives a real Hilbert space $\mathcal H$. Let $\phi(x)$ be the equivalence class of $e_x$, viewed in the completion. By the definition of the inner product, $$ \langle\phi(x),\phi(y)\rangle_{\mathcal H} = \langle e_x,e_y\rangle_0 = k(x,y). $$ This constructs the required feature map. The forward direction is the feature-map criterion proved above. $\square$

Building New Kernels From Old Ones

Once a formula is known to be a kernel, it can be combined with other kernels using operations that preserve positive semidefiniteness. The following result is useful for designing candidates, but its hypotheses matter: the weights in the sum must be nonnegative, and the product is the pointwise product on the same domain.

Theorem (Sum and product constructions): If $k_1$ and $k_2$ are kernels on $\mathcal X$, then $k_1+k_2$, $c k_1$ for $c\geq 0$, and the pointwise product $k_1k_2$ are kernels on $\mathcal X$. Therefore, every finite sum of kernels with nonnegative weights is also a kernel.

Proof. Let $\phi_1$ and $\phi_2$ be feature maps for $k_1$ and $k_2$, which exist by the feature-representation theorem. For the sum, use the direct-sum Hilbert space and the map $x\mapsto(\phi_1(x),\phi_2(x))$. Its inner product at $x,y$ is $k_1(x,y)+k_2(x,y)$. For $c\geq 0$, the map $x\mapsto\sqrt c\,\phi_1(x)$ represents $c k_1$, including the zero kernel when $c=0$.

For the product, use the Hilbert-space tensor product $\mathcal H_1\otimes\mathcal H_2$, in which elementary tensors satisfy $\langle u_1\otimes u_2,v_1\otimes v_2\rangle=\langle u_1,v_1\rangle\langle u_2,v_2\rangle$. The map $x\mapsto\phi_1(x)\otimes\phi_2(x)$ therefore has inner product $$ \langle\phi_1(x)\otimes\phi_2(x),\phi_1(y)\otimes\phi_2(y)\rangle = k_1(x,y)k_2(x,y). $$ Each construction has a feature map, so each resulting function is a kernel by the feature-map criterion. Repeating the sum construction proves the finite-sum claim. $\square$

Worked Example: A Product Kernel and Its Feature Map

Take $k_1(x,y)=1+xy$ on $\mathbb R$, already represented by $(1,x)$, and form its pointwise square: $$ k(x,y)=k_1(x,y)k_1(x,y)=(1+xy)^2. $$ The product construction guarantees that $k$ is a kernel. An explicit feature map is $$ \phi(x)=(1,\sqrt{2}x,x^2)\in\mathbb R^3, \qquad \langle\phi(x),\phi(y)\rangle =1+2xy+x^2y^2=(1+xy)^2. $$

For the points $0$ and $1$, the Gram matrix is $$ K= \begin{pmatrix} 1&1\\ 1&4 \end{pmatrix}. $$ For coefficients $a_1,a_2$, its quadratic form is $$ a^\mathsf{T}Ka=a_1^2+2a_1a_2+4a_2^2=(a_1+a_2)^2+3a_2^2\geq 0. $$ This checks the two-point case directly; the feature map establishes the result for all finite lists of real inputs.

A Practical Diagnostic and a Common Pitfall

A reliable workflow separates rejection from certification. To reject a formula, one explicit counterexample suffices. To certify it, give an argument covering arbitrary finite lists, usually by exhibiting a feature map or applying a proved construction rule.

Check the domain and symmetry.
Verify that the formula is defined for every pair in the stated domain and that swapping its arguments leaves it unchanged.

Search for a small failure.
Choose a few inputs, form the Gram matrix, and try a coefficient vector that makes its quadratic form negative. A successful counterexample disproves validity.

For a proof, establish the universal condition.
Construct an inner-product feature map or derive the formula from valid kernels using the sum, nonnegative scaling, or product construction.

A common mistake is to see nonnegative diagonal values, or to test one Gram matrix with nonnegative eigenvalues, and conclude that the formula is a kernel. The diagonal check only tests the one-point quadratic forms; a finite collection of successful checks still covers only those particular points. For example, $1-xy$ has $k(0,0)=1$ and $k(1,1)=0$, both nonnegative, yet the two-point quadratic form above equals $-1$. The correction is to use a general proof for every finite list when certifying a kernel, and to remember that one failing list is enough to rule one out.

Key takeaway: A real kernel is symmetric and has positive semidefinite Gram matrices on every finite input list. Use counterexamples to disprove a candidate and a feature-map representation or a valid closure construction to prove it.

Check Your Understanding

Use the definition and constructions to answer the following questions.

Why is symmetry required before a candidate can be a real kernel?
For a symmetric candidate, what does one negative Gram-matrix quadratic form establish? What does one nonnegative quadratic form establish?
Explain why nonnegative diagonal values do not by themselves establish that a function is a kernel.
Give a feature map for $k(x,y)=2+2xy$ on $\mathbb R$, and use it to justify the kernel claim.
Why must the coefficient $c$ be nonnegative in the construction $c k_1$?
If $k_1$ and $k_2$ are kernels on the same domain, what feature map represents their pointwise product?