Test for linear separability Is there a way to test linear separability of a two-class dataset in high dimensions? My feature vectors are 40-long.
I know I can always run logistic regression experiments and determine hitrate vs false alarm rate to conclude whether the two classes are linearly separable or not but it would be good to know if there already exists a standard procedure to do that.
 A: Well, support vector machines (SVM) are probably, what you are looking for. For example, SVM with a linear RBF kernel, maps feature to a higher dimenional space and tries to separet the classes by a linear hyperplane. This is a nice short SVM video illustrating the idea.
You may wrap SVM with a search method for feature selection (wrapper model) and try to see if any of your features can linearly sparate the classes you have.
There are many interesting tools for using SVM including LIBSVM, MSVMPack and Scikit-learn SVM.
A: Computationally the most effective way to decide whether two sets of points are linearly separable is by applying linear programming. GLTK is perfect for that purpose and pretty much every highlevel language offers an interface for it - R, Python, Octave, Julia, etc.
With respect to the answer suggesting the usage of SVMs:
Using SVMs is a sub-optimal solution to verifying linear separability for two reasons:


*

*SVMs are soft-margin classifiers. That means a linear kernel SVM might settle for a separating plane which is not separating perfectly even though it might be actually possible. If you then check the error rate it is going to be not 0 and you will falsely conclude that the two sets are not linearly separable. This issue can be attenuated by choosing a very high cost coefficient C - but this comes itself at a very high computational cost.

*SVMs are maximum-margin classifiers. That means the algorithm will try to find a separating plane that is separating the two classes while trying to stay away from both as far as possible. Again this is a feature increasing the computational effort unnecessarily as it calculates something that is not relevant to answering the question of linear separability.

Let's say you have a set of points A and B:

Then you have to minimize the 0 for the following conditions:
(The A below is a matrix, not the set of points from above)

"Minimizing 0" effectively means that you don't need to actually optimize an objective function because this is not necessary to find out if the sets are linearly separable. 
In the end 
() is defining the separating plane.


In case you are interested in a working example in R or the math details, then check this out.
A: Linear Perceptron is guaranteed to find a solution if one exists.
This approach is not efficient for large dimensions. Computationally the most effective way to decide whether two sets of points are linearly separable is by applying linear programming as mentioned by @Raffael.
A quick solution would be to solve a perceptron. A code with an example to solve using Perceptron in Matlab is here
