Solving Nonlinear SVM in Linear Time? A Nyström Approximated SVM with Applications to Image Classification∗

In this paper, we improve the efficiency of kernelized support vector machine (SVM) for image classification using linearized kernel data representation. Inspired by Nyström approximation, we propose a decomposi-tion technique for converting the kernel data matrix into an approximated primal form. This allows us to apply the approximated kernelized data in the primal form of linear SVMs, and achieve comparable recogni-tion performance as nonlinear SVMs do. Several ben-efits can be observed for our proposed method. First, we advance basis matrix selection for decomposing our proposed approximation, which can be viewed as fea-ture/instance selection with performance guarantees. More importantly, the proposed selection technique sig-nificantly reduces the computation complexity for both training and testing. Therefore, the resulting computa-tion time is comparable to that of linear SVMs. Exper-iments on two benchmark image datasets will support the use of our approach for solving the tasks of image classification.