"...if the data is linearly separable"

I keep hearing this phrase as a precursor to many algorithms, but I am not sure how exactly one goes about finding out if the data is indeed, linearly separable.

Of course, if the data has dimensionality $d\leq3$ we can always go about plotting it I suppose, but what is/are the methods involved exactly in figuring out if/when higher dimensional data ($d \geq 4$) is indeed linearly separable? What techniques are there?

• In most such cases, one runs the algorithm, which will find a linear separator if one exists.
– whuber
Commented Nov 10, 2014 at 15:05
• @whuber This was my suspicion as well. It seems like there is no canonical method besides try and see? Commented Nov 10, 2014 at 15:06
• Finding a solution and testing whether a solution exists are different problems. A linear separator exists if and only if no point in one set lies within the convex hull of the other and vice versa. Unfortunately it is not easy to compute convex hulls of $n$ points in high dimensions $d$; the optimal time is $O(n\log n + n^{\lfloor d/2 \rfloor})$. Checking inclusion without explicitly computing the hull is easier, but still complicated: see the discussion at stackoverflow.com/questions/4901959.
– whuber
Commented Nov 10, 2014 at 15:24
• Practical problems are almost never linearly separable, but linear models often yield acceptable performance. For most methods, linear models can be trained very fast, so fortunately it often doesn't take much computational resources to just try and see as whuber mentioned. Commented Nov 10, 2014 at 16:11

• (+1) I believe the idea of a tour goes back to Dan Asimov (1985), who has been a co-author of yours. I was therefore surprised to see no mention of Asimov at all in your tourr documentation.