I have the following function
$$
K(x, y) = \begin {cases}
1, & if ||x – y||_2 \le 1 \\
0, & otherwise
\end{cases}
$$
I'd like to prove (or disprove) that it's a valid kernel function.
In order for a function to be a kernel, I understand that I have to prove that the kernel matrix is symmetric and positive definite.
It's obvious that the kernel matrix for the above function is symmetric and positive, but how do I prove (or disprove) its definiteness?
Best Answer
For this kernel to be positive definite, the following inequality must be verified for every $n \in \mathbb N_+$, $x_1, \dots , x_n \in \mathbb R$ and $a_1, \dots , a_n \in \mathbb R$: $$ \mathcal S = \sum_{i,j=1}^n a_i a_j K(x_i, x_j) \geq 0 $$
Let's take $n=3$, $a_1 = a_2 = 1$ and $a_3 = -1$. Let's suppose that $x_2 = 0$, $x_3 = 1$ and $x_1 = 2$, so that $$ K(x_1, x_2) = 0,$$ $$ K(x_2, x_3) = 1,$$ $$ K(x_1, x_3) = 1.$$
Thus, $$ \mathcal S = a_1^2 + a_2^2 + a_3^2 + 2a_2a_3 + 2a_1a_3$$ $$ \mathcal S = -1$$
$K$ is therefore not positive definite.