1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Can you provide a link to the article in question? $\endgroup$ Commented Apr 13, 2013 at 16:36
  • $\begingroup$ @MichaelGrant. I have added the link to the paper $\endgroup$
    – user34790
    Commented Apr 13, 2013 at 17:06

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – user34790
    Commented Apr 13, 2013 at 14:20
  • $\begingroup$ For the linear SVM you never need to form the kernel. $\endgroup$ Commented Apr 13, 2013 at 16:26
  • $\begingroup$ 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. $\endgroup$ Commented Apr 13, 2013 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.