# Confusion related to svm optimization

I was reading thispaper related to kernel SVM. It states

Support Vector Machine (SVM) (Cortes and Vap- nik, 1995) as the state-of-the-art classification algo- rithm has been widely applied in various scientific do- mains. The use of kernels allows the input samples to be mapped to a Reproducing Kernel Hilbert S- pace (RKHS), which is crucial to solving linearly non- separable problems. While kernel SVMs deliver the state-of-the-art results, the need to manipulate the k- ernel matrix imposes significant computational bottle- neck, making it difficult to scale up on large data.

I didn't get what they mean by manipulate the kernel matrix. I mean lets say I am using the RBF kernel. Then my kernel matrix will have elements of the form

$exp^{\sigma {||x_i-x_j||}_2}{}$

which I can calculate once and then have it there. So what is meant by kernel manipulation

• Can you provide a link to the article in question? – Michael Grant Apr 13 '13 at 16:36
• @MichaelGrant. I have added the link to the paper – user34790 Apr 13 '13 at 17:06

They are simply referring to the fact that the kernel matrix itself is a central quantity in the algorithm. The problem is that it is $O(n^2)$ in size, where $n$ is the number of points being examined. So the storage and computational requirements surrounding the kernel matrix rapidly become impractical as $n$ gets large.

• Thats what I didn't get even in the linear svm, we can have the matrix which simply consists of the elements $x^Tx$. So it also consumes space isn't it? – user34790 Apr 13 '13 at 14:20
• For the linear SVM you never need to form the kernel. – Michael Grant Apr 13 '13 at 16:26
• I'm hoping someone else can provide a fuller answer---I am out of town an responding on my iPhone ;) Honestly I think context will help. Kernel methods are styled as a means of regaining efficiency. But it still requires solving a fuller QP. – Michael Grant Apr 13 '13 at 16:45