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 1


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.

  1. $\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})$$

  2. $\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.