In support vector machines (SVMs) and other Kernel based methods, like Gaussian processes, the Kernel replaces the inner product of two feature vectors $k(x_n,x_m)=x_n^Tx_m$. The Gaussian kernel
$$k(x_n,x_m) = \exp(- \frac{\theta}{2} \lVert x_n-x_m\rVert^2)$$ is a valid kernel function when $\theta \ge 0$. $\theta$ then plays the role of the inverse variance (precision).
My question is, is this function still a valid kernel function for SVMs and Gaussian processes when $\theta<0$?
Best Answer
This reasoning is essentially that of Sycorax's answer, but no need to resort to that theorem:
Consider two distinct points $x$ and $y$. For $\theta<0$, their Gram matrix is $$ \begin{bmatrix} k(x, x) & k(x, y) \\ k(x, y) & k(y, y) \end{bmatrix} = \begin{bmatrix} 1 & \alpha \\ \alpha & 1 \end{bmatrix} $$ where $\alpha = k(x, y) = \exp\left( - \frac{\theta}{2} \lVert x - y \rVert^2 \right) = \exp\left( \tfrac12 \lvert{\theta}\rvert \lVert x - y \rVert^2 \right) > 1$, since the argument to $\exp$ is strictly positive.
The characteristic polynomial of this Gram matrix gives $(\lambda - 1)^2 - \alpha^2 = 0$, so that $\lvert \lambda - 1 \rvert = \alpha$, and the eigenvalues of this matrix are $1 + \alpha$ and $1 - \alpha$. Since $\alpha > 1$, that second eigenvalue is negative, and the kernel is not psd.