Kernels and finite maps

Question

Let $\bf{x}, \bf{z} \in \mathbb{R}^n$. If the Gaussian kernel is defined by:

$$K(\bf{z}, \bf{x}) = \exp\left( - \frac{\|\bf{z} - \bf{x}\|_2^2}{\sigma^2}\right) $$

I'd like to know if there is a finite-dimensional feature map representation. In other words, does there exist some $\phi : \mathbb{R}^n \to \mathbb{R}^k$ such that

$$K(\bf{z}, \bf{x}) = \phi(\bf{z}) \cdot \phi(\bf{x}) $$

The infinite map is given in the following answer: https://stats.stackexchange.com/questions/69759/feature-map-for-the-gaussian-kernel, but if the finite map does not exist, could anyone provide an argument/proof for why this is so?

Answer 1

The finite map does not exist.

Suppose, for contradiction, that the finite map did exist. Consider the sequence of points $$\mathbf x_m := (m\sigma, 0, \dots, 0) \ \ \ {\rm for \ } m \in \mathbb N,$$ and observe that $$ \phi(\mathbf x_m) . \phi(\mathbf x_m) = 1 \ \ \ {\rm for \ all \ } m \in \mathbb N$$ and $$ \phi(\mathbf x_m) . \phi(\mathbf x_{m'}) \leq e^{-1} \ \ \ {\rm when \ } m \neq m'.$$

So if $\phi$ is a map into a finite-dimensional Euclidean space $\mathbf R^k$, then the vectors $\phi(\mathbf x_m)$ form a infinite set of vectors on the unit sphere in $\mathbf R^k$ such that the angle between any two of these vectors is greater than or equal to $\cos^{-1} (e^{-1})$. But since the unit sphere only has finite "surface area", it is impossible for such an infinite set of vectors to exist, hence the contradiction.

Answer 2

@Kenny Wong. An even simpler proof : if such a $\phi$ exist, taking $x=z$, one would have

$$K(x,x)=\underbrace{\exp(-0)}_{1}=\phi(x)^2$$

Thus $\forall x, \ \phi(x)=\pm 1$.

Assuming continuity for $\phi$, we conclude that $\phi$ is constant with constant value either $+1$ or $-1$, yielding a contradiction, because gaussian density is not a constant.