I'm having trouble trying to show that the linear kernel is a kernel because its Gram matrix is symmetric and positive semi-definite. Can anyone help me?
1 Answer
$\begingroup$
$\endgroup$
I assume you mean a kernel of the form $$K(\boldsymbol{x},\boldsymbol{y}) = \boldsymbol{x}^{T}\boldsymbol{y}$$ where we have $\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^{d}$. We need to show symmetry and positive definiteness of the function.
$\textit{Symmetry: }$ This is easy and follows directly from the symmetry of the dot product: $$K(\boldsymbol{x}, \boldsymbol{y}) = \boldsymbol{x}^{T}\boldsymbol{y} = \boldsymbol{y}^{T}\boldsymbol{x} = K(\boldsymbol{y}, \boldsymbol{x})$$
$\textit{Positive-Definiteness: }$ We need to prove that for every $\boldsymbol{c} \in \mathbb{R}^{n}$ and for any set of observations $\boldsymbol{x}_1, \dots, \boldsymbol{x}_n \in \mathbb{R}^{d}$, it holds: $$\sum_{i=1}^{n}\sum_{j=1}^{n}c_ic_jK(\boldsymbol{x}_i, \boldsymbol{x}_j) \geq 0$$ Plugging in the specific form of our kernel we see that $$\sum_{i=1}^{n}\sum_{j=1}^{n}c_ic_j\boldsymbol{x}_i^{T} \boldsymbol{x}_j = \left(\sum_{i=1}^{n}c_i\boldsymbol{x}_i\right)^{T}\left(\sum_{j=1}^{n}c_j \boldsymbol{x}_j\right) = {||}\sum_{i=1}^{n}c_i\boldsymbol{x}_i{||}_2^{2} \geq 0$$ where we used the double sum property $$\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^{n}b_i\right) = \sum_{i=1}^{n}\sum_{j=1}^{n}a_ib_j$$ This shows the positive definiteness of $K$ and hence $K$ is a kernel.
If you have a kernel with a bias $\beta>0$ $$K_{\beta}(\boldsymbol{x},\boldsymbol{y}) = \boldsymbol{x}^{T}\boldsymbol{y} + \beta$$ we can just reduce the problem to the above kernel $K$ by augmenting $\boldsymbol{x}$ with the coordinate $\sqrt{\beta}$.
Notice that $\beta>0$ is necessary, otherwise we don't get a kernel since $K_{\beta}(\boldsymbol{0},\boldsymbol{0}) = \beta <0$ violates positive definiteness. Hence the square-root $\sqrt{\beta}$ is well-defined.
