SVM has relatively low classification rate for high-dimensional data even though 2-D projections show they are separable I have another problem with 14000 features and 500 training samples. It is a binary classification problem and approximately in the form of an ellipse. My classification accuracy using the 2nd degree polynomial Kernel and via CV is ~ 80%. However, I've randomly tried projecting the data onto 2-D, that is I just pick out two features and project them, and find that there are several combinations that give me 100% separation. I've also used the RB kernel and the classification accuracy is ~70% for that. Does anyone have a reason why this is happening?
This is the code I'm using for libsvm...
% train SVM model
model = svmtrain2(Y(train_vec,1),X(train_vec,:),['-t 1 ' '-d 2 ' '-g ' num2str(grid_data(i,1)) ' ' '-r ' num2str(grid_data(i,2)) ' ' '-c ' num2str(C)]);
% test model on test set 
[predict_label, accuracy, dec_values] = svmpredict(Y(test_vec,1),X(test_vec,:),model); 

 A: I didn't see anything wrong with the results you had. As others pointed out already, you are facing a typical $P \gg N$ situation, where the number of predictors, i.e., features, is much greater than the number of instances.
In this situation, SVM is generally a good choice, as its maximum margin property gives some guarantees on the generalization performance. But in this situation, I would go for a linear kernel instead of a polynomial or RBF kernel. Because a linear kernel with 14000 features is already very powerful. If you later find out that the representation power of linear kernel is not enough, you can then try some more powerful kernels instead.
As you mentioned that the data are well separable with fewer predictors, you might want to get rid of some predictors in the first place. In general, we try to avoid the $P \gg N$ situation. Maybe you want to use some Lasso methods to do some implicit feature selection for you.
A: From Gaussian Processes for Machine Learning by Rasmussen:

In a feature space of dimension $N$, if $N > n$ then there will always be a separating hyperplane. However this hyperplane may not give rise to good generalization performance, especially if some of the labels are incorrect.

That is, if you have more dimensions than data points the data will be linearly separable, but  it doesn't necessarily mean that the data can be classified perfectly.
A: When there are more features than patterns, a linear kernel is generally a good idea as the other answers suggest (+1), however the really important thing to do then is to set the regularisation parameter (C) carefully (using e.g. cross-validation).  It is largely the regularisation of support vector machines that gives rise to their good generalisation performance (simply ridge regression with good choice of ridge parameter is often just as good in practice).
