# Impact of data dimensionality on computation complexity of SVM?

What is the impact of data dimensionality on computation complexity of SVM? I found on the literature that the complexity of SVM is $O(N^3)$, where $N$ is the number of training examples. If the number of dimension (e.g., $D$) does not impact the training time why it s better to reduce the dimensionality for training high-dimension dataset? Is it just to avoid overfitting?

BTW, I m using SVDD (support vector data description) from RRTools.

The O($N^3$) training complexity involves $n^2$ dot products and $n^3$ inverse of kernel matrix (A.Bordes et al Fast Kernel Classiﬁers with Online and Active Learning). However, it is also shown that the runtime of linear SVM optimization may decrease as the training size $N$ increases (Shai Shalev-Shwartz et al. SVM Optimization: Inverse Dependence on Training Set Size).
Mostly people view the training complexity independent of feature number, yet in SVM with RBF kernel, the training complexity is regarded as $O(dN^2)$ or $O(dN^3)$ ,where $d$ is the feature number (dimensionality)(Sreekanth Vempati et al.Generalized RBF feature maps for Efﬁcient Detection).
• @lennon310 Almost all kernels evaluations are dependent on $d$ since they typically involve an inner product. This is true for all common kernels (linear, polynomial, sigmoid, RBF). Apr 21 '14 at 20:37