Linear Kernel: Mathematical Deep Dive

1. Basic Definition

The Linear Kernel is defined as:

$k(x₁,x₂)=v\ast x₁ᵀ\ast x₂$

Where:

• $x₁,x₂\in ℝᵈ$ (d-dimensional real vector space)
• $v\in ℝ⁺$(positive real number)

2. Matrix Formulation

For a set of n input vectors $x₁,...,xₙ$, we can form a design matrix $X$:

$X=[x₁ᵀ;x₂ᵀ;...;xₙᵀ]$

The kernel matrix K is then:

$K=v\ast X\ast Xᵀ$

3. Properties

3.1 Positive Semi-Definiteness

The Linear Kernel is positive semi-definite (PSD), which is a crucial property for kernel functions. To prove this:

For any vector $\alpha \in ℝⁿ$:

$\alpha ᵀK\alpha =v\ast \alpha ᵀ(XXᵀ)\alpha =v\ast (Xᵀ\alpha )ᵀ(Xᵀ\alpha )=v\ast ||Xᵀ\alpha ||²\ge 0$

This holds because v > 0 and the squared norm is always non-negative.

3.2 Linearity in Feature Space

The Linear Kernel corresponds to a linear function in the feature space. If φ(x) = x is our feature map, then:

$k(x₁,x₂)=v\ast ⟨\phi (x₁),\phi (x₂)⟩$

Where $⟨·,·⟩$ denotes the inner product.

4. Connection to Linear Regression

The Linear Kernel is closely related to linear regression. In the context of Gaussian Processes:

$f(x)GP(0,k(x,x^{\prime }))$

With a Linear Kernel, this is equivalent to Bayesian Linear Regression:

$f(x)=w\ast x,wherewN(0,vI)$

5. Eigendecomposition

The eigendecomposition of K can provide insights:

$K=U\Lambda Uᵀ$

Where:

• $U$ is the matrix of eigenvectors
• $\Lambda$ is a diagonal matrix of eigenvalues

For the Linear Kernel:

• The rank of K is at most min(n,d)
• The non-zero eigenvalues correspond to the directions of maximum variance in the data

6. Gram Matrix Computation

In practice, we often work with the Gram matrix. For inputs $X=[x₁,...,xₙ]$ and $Y=[y₁,...,yₘ]$ :

$K_{X}Y=v\ast XYᵀ$

Elements: $K_{ij}=v\ast x_iᵀ\ast y_j$

7. Derivative

The derivative of the kernel with respect to its inputs is useful for optimization:

$\frac{\partial k(x_1,x_2)}{\partial x_1}=v\cdot x_2$

$\frac{\partial k(x_1,x_2)}{\partial x_2}=v\cdot x_1$

8. Variance Parameter

The variance parameter v scales the kernel:

$\frac{\partial k(x_1,x_2)}{\partial v}=x_1^{\mathrm{\top }}{x}_2$

This gradient is used when learning v from data.

9. Relation to Distance Metrics

The Linear Kernel is related to the Euclidean distance:

$||x₁-x₂||²=(x₁-x₂)ᵀ(x₁-x₂)=x₁ᵀx₁+x₂ᵀx₂-2x₁ᵀx₂$

If x₁ and x₂ are normalized $(||x₁||=||x₂||=1$), then:

$k(x₁,x₂)\propto 1-½||x₁-x₂||²$

This shows how the kernel relates to similarity in Euclidean space.