For the polynomial kernel, $K(x,y) = (x^Ty+c)^d$, the implicit feature space $\phi$ for which $K(x,y) = \phi(x)^T \phi(y)$ is of finite dimension and well known [1][2].

It is also well known that the implicit feature space of gaussian kernel $K(x,y) = e^{-||x-y||^2/2\sigma^2}$ is of infinite dimension [2].

My question is, what is the implicit feature space of power kernel?: $K(x,y) = ||x-y||^d$

What I have so far (may be wrong):

For $d = 2$ and $x,y \in ℝ^2$, $K(x,y) = ||x-y||^2 = (x_1 - y_1)^2 + (x_2 - y_2)^2 = x_1^2 + y_1^2 -2x_1y_1 + x_2^2 + y_2^2 -2x_2y_2$

but I cant find any definition of $\phi(x) $ so that $K(x,y) = \phi(x)^T \phi(y)$

thanks in advance.


[1] https://en.wikipedia.org/wiki/Polynomial_kernel

[2] http://arxiv.org/pdf/0904.3664v1.pdf pags. 37-39


Unfortunately, wikipedia's definition of a kernel is not simple enough. Turns out, norm is not a kernel (and so is it's power).

Let's take this definition of a kernel (from here):

Definition. $k : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ is a kernel if

  1. $k$ is symmetric: $k(x,y) =k(y,x)$.
  2. $k$ is positive semi-definite, i.e., $\forall x_1,x_2,...,x_n \in \mathcal{X}$, the ”Gram Matrix” $K$ defined by $K_{ij}=k(x_i,x_j)$ is positive semi-definite. (A matrix $M \in \mathbb{R}^{n \times n}$ is positive semi-definite if $\forall a \in \mathbb{R}^n, a'Ma\ge0$.)

Now, let's prove that $\|x-y\|^d$ is not a kernel. Obviously, it satisfies the first property, so we need to show that there exists a set of vectors $x_1, \dots, x_n$ such that the "Gram Matrix" is not positive semi-define.

Let's take $x_1 = (0, 1)$ and $x_2 = (1, 1)$. Corresponding $K$ is $$ K = \left( \begin{array}{cc} \|x_1 - x_1\|^d & \|x_1 - x_2\|^d \\ \|x_2 - x_1\|^d & \|x_2 - x_2\|^d \end{array} \right) = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right) $$

One way to show that $K$ is not PSD is to show that it has negative eigenvalues. If we denote $\lambda_1, \lambda_2$ as its eigenvalues, we can find them using trace and determinant:

$$ \begin{align} \lambda_1 + \lambda_2 &= \text{Tr} K = 0 \\ \lambda_1 \lambda_2 &= \text{det} K = -1 \\ \end{align} $$

From which it follows that $\lambda_1 = 1, \lambda_2 = -1$ (the order doesn't matter). Having a negative eigenvalue $\lambda$ implies that there exists a vector $v$ (namely, an eigenvector corresponding to that eigenvalue) such that $v' K v = \lambda v' v = \lambda \|v\|^2 < 0$ which means that $K$ is not positive semi-definite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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