2
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – gunes
    Oct 13, 2019 at 20:39
  • $\begingroup$ 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. $\endgroup$
    – gunes
    Oct 13, 2019 at 20:43
  • 1
    $\begingroup$ Thanks! Very helpful! $\endgroup$
    – user11128
    Oct 13, 2019 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.