# Implicit feature space of Power Kernel

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)$

References

[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.