Sparse random projection for χ2 kernel linearization: Algorithm and applications to image classification

The χ2 kernel based support vector machines (SVMs) have achieved impressive performances in many image and text classification tasks. As a nonlinear kernel method, however, it does not scale well to large scale data, because the computation of the χ2 kernel matrix is intractable. To address this challenge, we propose a sparse random projection method to linearly approximate the χ2 kernel, so that the original nonlinear SVMs could be converted to linear ones. Then we are able to make use of the existing large scale linear SVMs training method efficiently. Experimental results on three popular image data sets (MNIST, rcv1.binary, Caltech-101) show that the proposed method can significantly improve the learning efficiency of the χ2 kernel SVMs and the improvement comes at almost no cost of accuracy.