Linear Kernel Function

machine-learning statistics

Definition

Linear Kernel Function

The linear kernel is the simplest kernel function, corresponding to the standard dot product in the original instance space. Formally, for two vectors $\mathbf{x},{\mathbf{x}}^{\prime }\in {\mathbb{R}}^d$:

$k(\mathbf{x},{\mathbf{x}}^{\prime })={\mathbf{x}}^{\top }{\mathbf{x}}^{\prime }$

This represents a identity feature map $\varphi (\mathbf{x})=\mathbf{x}$, meaning the “higher-dimensional” Hilbert space is identical to the input space.

Computational Efficiency

Runtime Complexity: Evaluating the linear kernel requires $O(d)$ operations, making it the most computationally efficient choice for large-scale datasets.

Applicability: It is the preferred choice when the data is already linearly separable or when the number of features $d$ is very large relative to the number of samples $n$ (e.g., in text classification with one-hot encoded words), as high-dimensional spaces are often linearly separable without further expansion.