# Is it true that in high dimensions, data is easier to separate linearly?

I have often seen the statement that linear separability is more easily achieved in high dimensions, but I don't see why. Is it an empirical fact? An heuristic? Plain nonsense?

-
I should have specified that I'm not talking about kernel methods but about data that has a lot of features. –  cpa Jul 31 '12 at 22:38

Trivially, if you have $N$ data points, they will be linearly separable in $N-1$ dimensions. Any structure in the data may reduce the required dimensionality for linear separation further. You might say that (a projection of) a data set either is or is not completely linearly separable, in which using any (projection into) dimensionality lower than $N-1$ requires either additional properties of the data, of the projection into this higher dimensionality, or can be viewed as a heuristic (for instance in the case of random projections). In general we usually do not care to much about precise separability, in which case it is sufficient that we can meaningfully separate more data points correctly in higher dimensions.

-
Ok, I thought there'd be a more combinatorial argument but that's ok for me! Thanks! –  cpa Aug 2 '12 at 8:44