# Is a kernel space necessarily high dimensional?

It's very possible that I'm misunderstanding one or more terms here, so I will just try to explain what I understand (and why it doesn't make sense) :)

Say I have an $N$x$D$ data matrix, i.e. $N$ samples with $D$ features, and I compute an $N$x$N$ kernel out of this data. Now, according to the first answer here, I have computed the similarities in a high dimensional space without explicitly computing where the points lie in this space.

Now, is this necessarily true? What if $D$ > $N$ ? Then I actually would have computed the similarities in a lower dimensional space, right? If not, I would appreciate an explanation why :)

Thanks for any help,

The reason is in the mapping. If you use a linear mapping, then the VC dimension is n+1 (see A Tutorial on Support Vector Machines for Pattern Recognition), where n is the number of data points. Now, why mapping to a higher dimensional space?. The function counting theorem tells you that separability increases with the number of dimensions (for a given number of data points). The question is then how to do it in a computationally efficient manner.

Now, as soon as you use a non-linear kernel you have a bigger number of dimensions (because you have interaction terms. For example if you have (1+xy)^2 and expand it, then you have linear and quadratic terms). Notice that you compute the similarity without expanding the expression, you do not explicitly compute any mapping. The extreme case is the RBF kernel. Please refer to the first paper for a detail account of this point.