15
$\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$
3
  • 1
    $\begingroup$ Is this question more appropriate for Mathematics? $\endgroup$
    – Leo
    Commented Sep 20, 2012 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
    Commented Sep 28, 2012 at 7:36
  • $\begingroup$ @Nick Alger: maybe this helps: stats.stackexchange.com/questions/80398/… $\endgroup$
    – user83346
    Commented Aug 22, 2015 at 8:33

2 Answers 2

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.

$\endgroup$
3
$\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.

$\endgroup$
1
  • $\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
    Commented Aug 22, 2015 at 8:36

Your Answer

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

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