Kernel Confusion

Question

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!

Answer 1

For Q1, you can prove both way. First approach is typically harder since you explicitly need to find a high dimensional representation (that may also be non-unique).

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.