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

Question

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?

Answer 1

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.

Answer 2

I'm not sure if it matters whether the data actually has a high dimensionality or whether data is projected into a higher dimension. In the latter case, it is true that it's easier to linearly separate something projected into a higher dimension, hence the whole idea of kernel methods. (See Cover's Theorem, etc.)

My typical example is a bullseye-shaped data set, where you have two-dimensional data with one class totally surrounded by another. Not linearly separable in 2 dimensions, but project it into 3 dimensions, with the third dimension being the point's distance from the center, and it's linearly separable.

Answer 3

I think what you might be asking about is the use of kernels to make a data set more compatible with linear techniques. A short piece about this is available here: http://ldtopology.wordpress.com/2012/05/27/making-linear-data-algorithms-less-linear-kernels/.