14
$\begingroup$

How to prove that for the radial basis function $k(x, y) = \exp(-\frac{||x-y||^2)}{2\sigma^2})$ there is no finite-dimensional feature space $H$ such that for some $\Phi: \text{R}^n \to H$ we have $k(x, y) = \langle \Phi(x), \Phi(y)\rangle$?

$\endgroup$
  • 1
    $\begingroup$ Is this question more appropriate for Mathematics? $\endgroup$ – Leo Sep 20 '12 at 0:37
  • 1
    $\begingroup$ One possible plan of attack would be to exhibit a subspace of $H$ that is not closed. $\endgroup$ – Nick Alger Sep 28 '12 at 7:36
  • $\begingroup$ @Nick Alger: maybe this helps: stats.stackexchange.com/questions/80398/… $\endgroup$ – user83346 Aug 22 '15 at 8:33
11
+50
$\begingroup$

The Moore-Aronszajn theorem guarantees that a symmetric positive definite kernel is associated to a unique reproducing kernel Hilbert space. (Note that while the RKHS is unique, the mapping itself is not.)

Therefore, your question can be answered by exhibiting an infinite-dimensional RKHS corresponding to the Gaussian kernel (or RBF). You can find an in-depth study of this in "An explicit description of the reproducing kernel Hilbert spaces of Gaussian RBF kernels", Steinwart et al.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Assume that Gaussian RBF kernel $k(x, y)$ is defined on domain $X \times X$ where $X$ contains an infinite number of vectors. One can prove (Gaussian Kernels, Why are they full rank?) that for any set of distinct vectors $x_1, ..., x_m \in X$ matrix $(k(x_i, x_j))_{m \times m}$ is not singular, which means that vectors $\mathrm\Phi(x_1), ..., \mathrm\Phi(x_m)$ are linearly independent. Thus, a feature space $H$ for the kernel $k$ cannot have a finite number of dimensions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Here you find a more 'intuitive' explanation that the $\Phi$ can map onto a spave of dimension equal to the size of the training sample, even for an infinite training sample: stats.stackexchange.com/questions/80398/… $\endgroup$ – user83346 Aug 22 '15 at 8:36

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.