The cost of computing similarities is definitely linear or lower, wrt. to features. But overall, the Kernel SVM will scale to the order of n^3 wrt. to the numbe

The cost of computing similarities is definitely linear or lower, wrt. to features. But overall, the Kernel SVM will scale to the order of n^3 wrt. to the number of points. In that sense, focussing on the number of features may not make a lot of sense. PCA isn't lossless either. We are definitely trading off some richness in the data for efficiency. When the gain in efficiency is negligible (as is the case with SVMs) the trade off doesn't look as tempting. I am student in the area as well, so take my words with appropriate caution.