Mercer's theorem and valid kernels: Definition & Examples

Mercer's theorem represents a continuous positive semidefinite kernel on a compact domain through eigenfunctions of an associated integral operator. It explains how a similarity rule can encode feature coordinates. For a quant using a custom similarity in a kernel method, the immediate safeguard is more basic: every finite kernel matrix must be positive semidefinite. A plausible-looking similarity score need not satisfy that requirement.

Validity asks about every finite sample

For real-valued inputs from a set $X$ , a symmetric function $k:X\times X\to\mathbb{R}$ is a positive semidefinite kernel when

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

for every sample size

n

, every choice of inputs

x_1,\ldots,x_n

and every real coefficient vector

c

. Equivalently, every Gram matrix

K_{ij}=k(x_i,x_j)

is positive semidefinite (PSD). Here “positive” concerns quadratic forms, not individual entries. Some kernel literature calls this a positive definite kernel even though zero quadratic forms are permitted. Rasmussen and Williams, §4.1

A feature representation $k(x,z)=\langle\phi(x),\phi(z)\rangle$ proves the condition directly:

c^\top Kc=\left\lVert\sum_i c_i\phi(x_i)\right\rVert^2\geq 0.

Conversely, the Moore–Aronszajn theorem gives every such kernel a unique reproducing kernel Hilbert space (RKHS), with canonical feature map

\phi(x)=k(\cdot,x)

. This existence result needs no compact domain or continuity assumption. The finite-Gram criterion is often loosely called “Mercer's condition” in machine learning; Mercer’s spectral expansion adds regularity assumptions. Sejdinovic and Gretton, Theorem 42 and §6

Two positive-looking matrices, different answers

Take the linear kernel $k(x,z)=xz$ on the real line and sample inputs $1$ and $2$ . Its Gram matrix is

A=\begin{pmatrix}1&2\\2&4\end{pmatrix}.

Its eigenvalues are $0$ and $5$ . More decisively, for arbitrary coefficients $a,b$ ,

\begin{pmatrix}a&b\end{pmatrix}A\begin{pmatrix}a\b\end{pmatrix}=(a+2b)^2\geq0.

The zero eigenvalue is allowed: PSD does not require invertibility. The kernel is globally valid because its feature map is simply $\phi(x)=x$ , not because this particular sample passed.

Now suppose a proposed similarity assigns the matrix

B=\begin{pmatrix}1&2\\2&1\end{pmatrix}

to two inputs. All entries are positive and the matrix is symmetric, yet its eigenvalues are $-1$ and $3$ . With $v=(1,-1)^\top$ ,

v^\top Bv=1-2-2+1=-2.

That single counterexample rules out the proposed rule as a PSD kernel on any domain containing those inputs. If used as a covariance matrix, it would assign a negative variance to their difference.

Two exact symmetric matrices: A has rows 1,2 and 2,4 with eigenvalues 0 and 5; B has rows 1,2 and 2,1 with eigenvalues minus 1 and 3. Unit-direction quadratic forms stay nonnegative for A but reach minus 1 for B at 135 degrees. The unnormalized contrast vector 1,minus 1 gives minus 2 for B.

Original exact example. The curves evaluate each quadratic form on unit-length vectors, so their extrema equal the matrix eigenvalues. The raw vector (1, −1) has squared length 2, explaining its value −2 rather than −1.

A successful Gram check certifies that matrix alone. Global validity requires a proof covering all finite choices, for example an explicit feature map. An eigensolver is useful for finding counterexamples; numerical tolerance should distinguish rounding near zero from a materially negative eigenvalue.

What Mercer adds

One standard real-valued version assumes a continuous PSD kernel $k$ on a compact metric space $X$ , and a finite Borel measure $\mu$ with full support: every nonempty open subset has positive measure. Define

(T_k f)(x)=\int_X k(x,z)f(z)\,d\mu(z).

This is a compact, positive, self-adjoint operator on $L^2(X,\mu)$ . For its positive eigenvalues $\lambda_j$ and corresponding continuous eigenfunctions $e_j$ , orthonormal in $L^2(X,\mu)$ , Mercer gives

k(x,z)=\sum_{j\in J}\lambda_j e_j(x)e_j(z).

The index set is at most countable; convergence is uniform on

X\times X

and absolute for each pair. Hence

\phi_j(x)=\sqrt{\lambda_j}e_j(x)

supplies feature coordinates. The sum may be finite. These conclusions use the stated assumptions; an arbitrary PSD kernel does not automatically have this particular continuous spectral representation. Sejdinovic and Gretton, §§6.1–6.2, Theorem 48

For a separate continuous example, restrict

k(x,z)=xz

X=[0,1]

and use Lebesgue measure. This domain differs from the earlier real-line sample, whose second input was

2

. There is just one positive operator eigenvalue:

\lambda_1=\frac13,\qquad e_1(x)=\sqrt3\,x,\qquad \int_0^1 e_1(x)^2\,dx=1.

Indeed, $T_ke_1=e_1/3$ and $(1/3)e_1(x)e_1(z)=xz$ . The operator eigenvalue $1/3$ belongs to a domain-and-measure problem; the earlier Gram eigenvalue $5$ belongs to a two-observation matrix. They are different objects.

For the matrix foundations, Positive (Semi-)Definite Matrices: Equivalent Characterisations develops the eigenvalue and quadratic-form tests (membership required for the full lesson; public preview available).

Sources

Dino Sejdinovic and Arthur Gretton, What is an RKHS? (2012), §4.5, Theorem 42; §§6.1–6.2, Theorem 48.
Carl Edward Rasmussen and Christopher K. I. Williams, Gaussian Processes for Machine Learning (2006), Chapter 4, §4.1, Gram matrices and positive semidefiniteness.

Validity asks about every finite sample

Two positive-looking matrices, different answers

What Mercer adds

Sources

Related terms

Kernel method and kernel trick

Positive semidefinite matrix