Large-Scale Support Vector Machine Training using Low-Dimensional Approximation of the Kernel Matrix
Training Support Vector Machines (regression and/or classification) involves solving a simply constrained quadratic programming problem that scales linearly with training set size. Unfortunately this makes solving large-scale problems with millions of training samples difficult if not impossible from both computational and storage considerations. A standard approach is to exploit the sparsity of the optimal solution (# of support vectors) as in decomposition/chunking or work with few variables at a time as in SMO. Yet another approach [5] is to exploit the low-rank nature of the kernel matrix. The applicability of this is limited clearly to those kernels that have a good low-rank approximation. This paper introduces the notion of low-dimensional approximation of the kernel matrix that naturally specializes to the methods in [5] for the low-rank case. Exact approximation results and approximate results based on computational considerations are given. The advantage of our scheme is that it directly translates to interior point methods for QP in [5]. Our approximation results may be of relevance in interior point methods for solving LPs approximately. Also, the approximation results in this paper should be of interest in statistical modeling with Gaussian Mixtures as well as Gaussian Process classification and regression.