Mercer's Condition and Valid Kernels

The kernel trick lets an SVM or kernel ridge regression operate as if it had mapped every data point into some enormous, possibly infinite-dimensional feature space and taken dot products there — without ever computing that mapping, just by plugging a kernel function $k(x, x')$ directly into the algorithm wherever a dot product would go. That substitution is only mathematically valid if $k$ really does correspond to some dot product in some feature space, for some mapping $\phi$. Not every two-input function has that property. Mercer's condition is the precise test for which functions qualify as legitimate kernels, and which are just similarity scores that happen to look kernel-shaped.

The analogy: a shortcut that only works for real distances

Suppose someone claims "I can compute the straight-line distance between any two cities without ever drawing a map, using this formula." That claim is only trustworthy if the formula genuinely corresponds to some consistent map — if it violates basic distance properties (like giving a city zero distance from a different city), no map could produce those numbers, and the "shortcut" is made up. Mercer's condition plays the same role for kernels: it tests whether $k(x,x')$ genuinely corresponds to "dot product after some feature mapping $\phi$," or is just an arbitrary similarity function with no consistent geometric picture behind it — in which case algorithms relying on the kernel trick can silently break.

The condition

A symmetric function $k(x, x')$ satisfies Mercer's condition if, for every finite set of points $x_1, \dots, x_n$, the $n \times n$ Gram matrix $K$ with entries $K_{ij} = k(x_i, x_j)$ is positive semi-definite — meaning for every real vector $c$,

$$\sum_{i=1}^n \sum_{j=1}^n c_i c_j\, k(x_i, x_j) \ge 0$$

Plain English: no matter which points you pick and how you weight them, this particular weighted double-sum of kernel values can never come out negative. If that holds for every possible finite set of points, Mercer's theorem guarantees a feature mapping $\phi$ exists (possibly infinite-dimensional) with $k(x,x') = \phi(x)\cdot\phi(x')$ — the kernel trick is then rigorously justified, and algorithms like the SVM dual and kernel ridge regression are guaranteed to have a well-posed (typically convex) optimization problem.

Worked example 1: verifying the linear kernel

Take $k(x,x') = x \cdot x'$ (ordinary dot product) — obviously valid, since it's already literally a dot product with $\phi(x)=x$. Check with two points $x_1=1, x_2=2$ and weights $c_1=3, c_2=-1$: Gram matrix $K = \begin{pmatrix}1 & 2\\2&4\end{pmatrix}$. The sum is $c_1^2 K_{11} + 2c_1c_2K_{12}+c_2^2K_{22} = 9(1)+2(3)(-1)(2)+1(4)=9-12+4=1 \ge 0$. Trying other weights always gives a non-negative result here because this Gram matrix is $vv^T$ for $v=(1,2)$, which is positive semi-definite by construction — any dot-product kernel automatically passes.

Worked example 2: a function that fails Mercer's condition

Consider $k(x,x') = -(x-x')^2$ (negative squared distance) as a candidate "similarity." Take one point $x_1 = 0$, weight $c_1=1$: the sum is just $k(0,0) = -(0)^2 = 0$, fine so far. But take two points $x_1=0, x_2=1$ with weights $c_1=1, c_2=1$: $K_{11}=0, K_{22}=0, K_{12}=K_{21}=-(0-1)^2=-1$. Sum $= 1(0)+2(1)(1)(-1)+1(0) = -2 < 0$. The condition fails — negative squared distance is not a valid kernel, because no feature mapping can produce dot products that go negative for a point against itself and combine this way; plugging it into an SVM's dual optimization would hand the solver a non-convex problem with no guarantee of a sensible solution.

A positive semi-definite matrix corresponds to a transformation that never flips space inside-out — watch how the eigenvalues here stay non-negative for a valid transform; a Gram matrix with a negative eigenvalue is the algebraic signature of a kernel that fails Mercer's condition.

What this means in practice

Every kernel used routinely in practice — linear, polynomial $(x\cdot x'+c)^d$, RBF $e^{-\gamma\|x-x'\|^2}$ — is chosen because it's known to satisfy Mercer's condition, which is why practitioners rarely derive the condition from scratch: they pick from this pre-verified library, or combine existing valid kernels (sums and products of valid kernels are themselves valid). The condition matters most when someone invents a custom "similarity function" for a domain-specific application and plugs it directly into an SVM or Gaussian process — without checking Mercer's condition, the resulting optimization may not even be convex.