Linear Kernel

Creator
Creator
Seonglae Cho
Created
Created
2024 Dec 6 15:6
Editor
Edited
Edited
2025 May 19 16:2
Refs
Refs

Dual representation of
Ridge regression

k(x,y)=xyk(x, y) = x\cdot y

Proof of valid kernel

Given the kernel k(xi,xj)=xixjk(x_i, x_j) = x_i \cdot x_j, we need to prove
i=1nj=1ncicjk(xi,xj)0\sum_{i=1}^n \sum_{j=1}^n c_i c_j k(x_i, x_j) \geq 0i=1nj=1ncicj(xixj)\sum_{i=1}^n \sum_{j=1}^n c_i c_j (x_i \cdot x_j)
Rearrange terms using the bilinearity of the dot product:
i=1nj=1ncicj(xixj)=(i=1ncixi)(j=1ncjxj)\sum_{i=1}^n \sum_{j=1}^n c_i c_j (x_i \cdot x_j) = \left( \sum_{i=1}^n c_i x_i \right) \cdot \left( \sum_{j=1}^n c_j x_j \right)Let v=i=1ncixi:(i=1ncixi)(j=1ncjxj)=vv\text{Let } v = \sum_{i=1}^n c_i x_i: \left( \sum_{i=1}^n c_i x_i \right) \cdot \left( \sum_{j=1}^n c_j x_j \right) = v \cdot v
Simplify using the definition of the Euclidean norm:
vv=v20v \cdot v = \|v\|^2 \geq 0
Therefore, for any cc and xx
i=1nj=1ncicjk(xi,xj)0.\sum_{i=1}^n \sum_{j=1}^n c_i c_j k(x_i, x_j) \geq 0.
 
 
 

Recommendations