Is the Gaussian Kernel still a valid Kernel when taking the negative of the inner function?

Question

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$?

Answer 1

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.

Answer 2

This is an extended comment, please don't judge me too harshly.

Mercer's theorem characterizes the positive semidefinite (PSD) kernel which is of interest to OP. Mercer provides two conditions for a valid kernel:

1. The function is symmetric: $f(x,y)=f(y,x)$.
2. The resulting kernel matrix $K_{n\times n}$ is PSD for all valid inputs, which implies that its eigenvalues are all nonnegative. (Kernels may be restricted to only consider specific intervals or sets, so it's feasible to define a kernel that is PSD for just some input values.)

Let's approach the problem by cases.

Note that $\theta=0$ results in a matrix of 1s. It has rank 1, and has the eigenvalue 1 once and the remaining $n-1$ of its eigenvalues are 0. Hence, it is PSD.

For $\theta>0$, the farther apart two points are, the smaller the similarity between them. Unless two points are identical, the off-diagonal elements of $K$ are less than 1, and the diagonal elements are 1.

We can use the same reasoning to show that for $\theta<0$, $K$ is not diagonally dominant; that is, non-idential elements will have larger entries on the off-diagonal than the diagonal (because $f(x,y;\theta<0)$ is convex with a minimum at 1). I think that we could get clever with the Girshgorin circle theorem to show that in this case, the matrix is indefinite, but I've tried and am stuck. I'll keep thinking about it.

Answer 3

After some more thinking I will make an attempt to answer my own question. From Bishop's Pattern Recognition and Machine Learning, p. 296, I take rules for building new Kernels from valid Kernels. Let $k_1$ be a valid Kernel then

$$ k(x_n,x_m) = f(x) k_1(x_n,x_m) f(x^T) $$ $$ k(x_n,x_m) = \exp(k_1(x_n,x_m)) $$

are again valid Kernels. Now we have

$$\frac{\theta}{2} \lVert x_n-x_m \rVert^2 = \frac{\theta}{2} x_n^T x_n + \frac{\theta}{2} x_m^T x_m - \theta x_n^T x_m$$

So

$$\exp (-\frac{\theta}{2} \lVert x_n-x_m \rVert^2)= \exp (-\frac{\theta}{2} x_n^T x_n) \exp (\theta x_n^T x_m) \exp (-\frac{\theta}{2} x_m^T x_m)$$

Hence by the second rule from above and since we know $x_n^T x_m$ is a valid kernel, $\exp (\theta x_n^T x_m) $ is a valid kernel if $\theta>0$, but it is not if $\theta<0$. By the first rule then $\exp (-\frac{\theta}{2} \lVert x_n-x_m \rVert^2)$ is a valid kernel if $\theta>0$ but not if $\theta<0$. I am not sure about this though. Comments welcome.