Mercer's Conditions

machine-learning linear-algebra

Definition

Mercer's Theorem

Let $\mathcal{X}$ be a compact metric space and let $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ be a continuous, symmetric function. Then $k$ is a valid kernel — i.e. there exists a Hilbert space $\mathcal{H}$ and a feature map $\varphi :\mathcal{X}\to \mathcal{H}$ such that

$$k(\mathbf{x},{\mathbf{x}}^{\prime })=⟨\varphi (\mathbf{x}),\varphi ({\mathbf{x}}^{\prime }){⟩}_{\mathcal{H}}$$

— if and only if $k$ is positive semi-definite. That is, for every finite set of points ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\in \mathcal{X}$ and every choice of coefficients $c_1,\dots ,c_n\in \mathbb{R}$:

$$\sum _{i=1}^n\sum _{j=1}^n{c}_i{c}_{j}k({\mathbf{x}}_i,{\mathbf{x}}_j)\ge 0$$

Consequence

Mercer’s theorem guarantees that the “kernel trick” is mathematically sound. Whenever a kernel satisfies the positive semi-definiteness condition, one can construct an implicit high-dimensional feature space and run linear algorithms there without ever computing $\varphi (\mathbf{x})$ explicitly.

Eigenfunction Expansion

When the conditions hold, the kernel admits a spectral decomposition:

$$k(\mathbf{x},{\mathbf{x}}^{\prime })=\sum _{m=1}^{\infty }{\lambda }_m{e}_m(\mathbf{x})e_m({\mathbf{x}}^{\prime })$$

where ${\lambda }_m\ge 0$ are non-negative eigenvalues and $e_m$ are the corresponding orthonormal eigenfunctions in $L^2(\mathcal{X})$. The feature map can then be taken as $\varphi (\mathbf{x})=(\sqrt{{\lambda }_m}{e}_m(\mathbf{x}){)}_{m=1}^{\infty }$.