# Kernel Confusion

Consider the function $$K(\vec{x},\vec{y})$$ where $$\vec{x},\vec{y} \in \mathbb{R}^n$$. I have been asked to check that this is a valid kernel.

Question 1

My understanding is that I can prove this in one of two ways:

1, I can show there exists a feature map $$\phi : \mathbb{R}^n \rightarrow \mathbb{R}^N$$ such that $$K(\vec{x}, \vec{y}) = \langle \vec{\phi}(\vec{x}), \vec{\phi}(\vec{y}) \rangle$$

2, I can show that $$K(\vec{x},\vec{y})$$ is positive semi-definite

Is my understanding correct here that these are both valid ways to show something is a kernel?

Question 2

Let's suppose I want to explicitly show positive semi-definiteness (as in case 2 above). I am unsure whether I do this by showing

(a) $$K(\vec{a}, \vec{a}) \geq 0$$

This case is kind of appealing since kernels are supposed to measure similarity between two vectors and so it only really makes sense for a vector to have a similarity with itself that is $$\geq 0$$.

(b) $$\vec{a}^T K(\vec{x},\vec{y}) \vec{a} \geq 0$$

In this case $$\vec{x}$$ and $$\vec{y}$$ define the kernel matrix and I need to show it is a positive semi-definite matrix for any other vector $$\vec{a} \in \mathbb{R}^n$$

I'd appreciate any help with my understanding on this.

Thanks!

For Q2, there is no such thing like $$K(a,a)$$ in general because $$a\in R^N$$ where $$K(x,y)$$ is of $$N\times N$$ ($$N$$ is number of elements in the dataset), and $$x,y\in R^n$$, where $$n$$ is the dimension of the inner product space where your data lies. So, you'll need to make sure your kernel matrix has no negative eigenvalues, i.e. PSD property.
• Yes, the combination. Because $K(x,y)$ will always be a scalar for any given $x,y$ pair (i.e. it is an inner product after all). Oct 13, 2019 at 20:39
• It's a general vector for showing semi-definiteness of $K$. The goal is to show the PSD property. If you have $K$, you can also find its eigenvalues and show that all of them are non-negative. There are various ways, $a$ is only a tool for showing it, with no special meaning to the best of my knowledge. Oct 13, 2019 at 20:43