I am using scikit-learn's SVM for the MNIST digit classification dataset. In order to improve the performance I extended the dataset by adding rotated samples. I was aware that SVM takes O(N^3) time to train the data, where N is the number of training vectors.
However even prediction seems to take increase polynomially, the number of test vectors is the same. Is there any explanation for this or some equation that relates prediction time to the number of training samples?
I am using a 3rd degree polynomial as the kernel with C=100.0.
Note: I am doing a group project to compare the performance of various methods so I can't use any other method as my teammates would have used those. I referred to a paper by Decoste and Scholkoph which uses Virtual SVM. However I don't think I can run this on my current system if I can't run a simple extended training set.