SVM Kernel Design in Python: Mercer's Theorem, Gram Matrix Positive-Definiteness, and Random Fourier Features

Introduction

https://yuhi-sa.github.io/en/posts/20260226_svm/1/ introduced SVM fundamentals and the kernel trick, listing linear, RBF, and polynomial kernels in a summary table. It never addressed the core questions: why can’t an arbitrary function serve as a kernel, and why is the RBF kernel said to correspond to an infinite-dimensional feature map? This article derives the validity condition for kernels — Gram-matrix positive semi-definiteness — from Mercer’s theorem, constructs an explicit feature map for the polynomial kernel and verifies it numerically, and uses Random Fourier Features (Rahimi & Recht, 2007) to make the RBF kernel’s infinite dimensionality tangible. We also quantify how the hyperparameter \(\gamma\) affects generalization.

Recap: The Kernel Trick

In the SVM dual problem derived in https://yuhi-sa.github.io/en/posts/20260226_svm/1/, data appears only through the inner product \(\mathbf{x}_i \cdot \mathbf{x}_j\) . Replacing this inner product with a kernel function \(K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)\) enables nonlinear classification without ever computing the high-dimensional feature map \(\phi\) explicitly. But not every two-argument function \(K(\mathbf{x}, \mathbf{y})\) qualifies for this role.

Mercer’s Theorem: The Validity Condition for Kernels

A function \(K(\mathbf{x}, \mathbf{y})\) can be written as \(K(\mathbf{x}, \mathbf{y}) = \phi(\mathbf{x}) \cdot \phi(\mathbf{y})\) for some feature map \(\phi\) (i.e., is a valid kernel) if and only if, for any finite set of data points \(\{\mathbf{x}_1, \ldots, \mathbf{x}_n\}\) , the Gram matrix

is positive semi-definite (all eigenvalues \(\geq 0\) ) — this is Mercer’s theorem. Intuitively, whenever the Gram matrix is positive semi-definite, its eigendecomposition \(K = V \Lambda V^\top\) directly supplies a coordinate system in which the matrix is literally an inner-product matrix of feature vectors (\(\phi(\mathbf{x}_i) = \sqrt{\Lambda} V_i\) ).

Experiment 1: Checking Gram-Matrix Positive-Definiteness Directly

For 50 random points in 3D, we computed the Gram matrix for the RBF kernel, the polynomial kernel, and an invalid kernel (\(K(\mathbf{x},\mathbf{y}) = -\|\mathbf{x}-\mathbf{y}\|\) ), then inspected the minimum eigenvalue.

import numpy as np

def rbf_kernel(X, gamma=0.5):
    sq = np.sum(X**2, axis=1)
    D2 = sq[:, None] + sq[None, :] - 2 * X @ X.T
    return np.exp(-gamma * D2)

def poly_kernel(X, degree=2, gamma=1.0, coef0=1.0):
    return (gamma * (X @ X.T) + coef0) ** degree

def invalid_kernel(X):
    sq = np.sum(X**2, axis=1)
    D2 = sq[:, None] + sq[None, :] - 2 * X @ X.T
    return -np.sqrt(np.maximum(D2, 0))  # negative distance: not a valid Mercer kernel in general

The RBF and polynomial kernels have minimum eigenvalues at or above zero (within floating-point tolerance), confirming positive semi-definiteness. Using the negative Euclidean distance directly as a kernel produces a strongly negative minimum eigenvalue, numerically confirming that it fails Mercer’s condition (negative Euclidean distance is indeed known not to be a positive-definite kernel in general).

Experiment 2: Explicit Feature Map for the Polynomial Kernel

Expanding the degree-2 polynomial kernel \(K(\mathbf{x},\mathbf{y}) = (\gamma\,\mathbf{x}\cdot\mathbf{y} + c)^2\) (with \(\mathbf{x},\mathbf{y}\in\mathbb{R}^2\) ) via the multinomial theorem yields an explicit 6-dimensional feature map

We computed the inner product \(\phi(\mathbf{x})\cdot\phi(\mathbf{y})\) directly using this map and compared it against the kernel function’s value.

def explicit_feature_map_deg2(x, gamma, coef0):
    x1, x2 = x
    return np.array([
        gamma * x1**2,
        gamma * x2**2,
        np.sqrt(2) * gamma * x1 * x2,
        np.sqrt(2 * coef0 * gamma) * x1,
        np.sqrt(2 * coef0 * gamma) * x2,
        coef0,
    ])

K(x,y) via kernel formula : 0.0018919198
K(x,y) via <phi(x),phi(y)>: 0.0018919198
abs diff: 3.70e-16

The kernel-function value and the explicit feature map’s inner product match to machine precision — direct evidence that the kernel trick really is a shortcut for a high-dimensional inner product.

The RBF Kernel Corresponds to an Infinite-Dimensional Feature Map

Unlike the polynomial kernel, the RBF kernel \(K(\mathbf{x},\mathbf{y}) = \exp(-\gamma\|\mathbf{x}-\mathbf{y}\|^2)\) has no finite-dimensional explicit feature map. Taylor-expanding the exponential shows why:

is a positively-weighted sum of infinite-degree polynomial kernels (each term \((\mathbf{x}\cdot\mathbf{y})^k\) is itself a valid kernel, and a positively-weighted sum of valid kernels is valid). The full RBF kernel factors as \(K(\mathbf{x},\mathbf{y}) = \exp(-\gamma\|\mathbf{x}\|^2)\exp(2\gamma\,\mathbf{x}\cdot\mathbf{y})\exp(-\gamma\|\mathbf{y}\|^2)\) , and since a positive diagonal scaling preserves positive semi-definiteness, the RBF kernel as a whole is valid too.

Experiment 3: Making the Infinite Dimensionality Tangible with Random Fourier Features

We can’t compute an infinite-dimensional feature map exactly, but Random Fourier Features (RFF; Rahimi & Recht, 2007) give a finite-dimensional randomized approximation. By Bochner’s theorem, the RBF kernel can be approximated using random frequencies \(\mathbf{w}\sim\mathcal{N}(0, 2\gamma I)\) and random phases \(b\sim\text{Uniform}(0,2\pi)\) as

(an explicit \(D\) -dimensional feature map built from \(D\) random features).

w = rng.normal(0, np.sqrt(2 * gamma), size=(D, d))
b = rng.uniform(0, 2 * np.pi, size=D)
def rff(X):
    proj = X @ w.T + b
    return np.sqrt(2.0 / D) * np.cos(proj)

We measured the RMSE between the true RBF kernel value and the RFF approximation over 200 pairs of 5-dimensional points, varying \(D\) .

Each 10x increase in \(D\) shrinks the RMSE by roughly \(1/\sqrt{10} \approx 0.32\) , matching the standard Monte Carlo convergence rate \(O(1/\sqrt{D})\) . This quantitatively demonstrates convergence toward the infinite-dimensional kernel as the number of random features grows. RFF is used in practice for exactly this reason: approximating a kernel SVM with a linear SVM (sklearn.svm.LinearSVC or sklearn.linear_model.SGDClassifier) reduces the computational cost from \(O(n^2)\) to \(O(n)\) for large datasets — this is what sklearn.kernel_approximation.RBFSampler implements.

Kernel Construction Rules: Building Custom Kernels

The set of valid kernels is closed under the following operations (so composing kernels this way always yields a valid kernel):

• Positive scalar multiplication: if \(K\) is valid, so is \(cK\) for \(c>0\)
• Sum: if \(K_1, K_2\) are valid, so is \(K_1 + K_2\)
• Product: if \(K_1, K_2\) are valid, so is \(K_1 \cdot K_2\) (elementwise product)

Using this, we checked the Gram matrix of a simple weighted sum of an RBF and a polynomial kernel, \(0.5K_{\text{RBF}} + 0.5K_{\text{poly}}\) : the minimum eigenvalue was \(0.000045\) (effectively non-negative), confirming validity. This construction principle is the theoretical basis for domain-informed custom kernels — e.g., combining a periodicity-capturing kernel with a trend-capturing kernel for time-series data (the same construction rules appear in Gaussian process regression, covered in https://yuhi-sa.github.io/en/posts/20260502_gaussian_process/1/).

The Effect of γ: From Underfitting to Overfitting

Using sklearn.datasets.make_moons (noise 0.25) for a nonlinear dataset, we fixed \(C=1.0\) and swept \(\gamma\) , measuring train/test accuracy and support-vector count with sklearn.svm.SVC.

At small \(\gamma\) (0.01) the decision boundary is too smooth to even fit the training data well — underfitting. Around \(\gamma=10\) , test accuracy peaks at 98.9% — the sweet spot. At \(\gamma=1000\) , training accuracy hits 100% while test accuracy collapses to 55.6% — severe overfitting (every one of the 210 training points becomes a support vector, each carving out an isolated, narrow Gaussian bump around itself — pure memorization). This experiment quantitatively confirms that the RBF kernel’s \(\gamma\) controls how quickly similarity decays in feature space: set it too high, and every point becomes its own isolated feature, destroying generalization.

Related Articles

• Support Vector Machine (SVM): Kernel Methods and Nonlinear Classification in Python - SVM fundamentals. This article is a deep dive into the mathematical justification for the kernel trick used there.
• Gaussian Process Regression (GPR) in Practice: Observation Noise and Hyperparameter Optimization - Uses the same kernel theory (RBF, construction rules) in the context of Bayesian regression.
• Bayesian Optimization: Theory and Python Implementation - Combines Gaussian processes with an acquisition function; shares the practical importance of kernel choice.
• k-Means vs. GMM: Clustering Theory and Python Implementation - A contrasting unsupervised method based on distance/similarity.
• SGD and Adam: Theory and Comparison - An SVM linearized via Random Fourier Features can be trained quickly with these gradient-descent-based classifiers.

References

• Vapnik, V. N. (1998). Statistical Learning Theory. Wiley.
• Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press.
• Rahimi, A., & Recht, B. (2007). Random features for large-scale kernel machines. Advances in Neural Information Processing Systems (NeurIPS).
• Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Chapter 6 (Kernel Methods).