On Sparsity of Soft Margin Support Vector Machines
Jochen Merker · Journal of Advances in Applied Mathematics · 2017
In supervised machine learning, a support vector machine (SVM) constructs from binary classified training data a linear classifier by solving a linearly constrained convex optimization problem.Depending on the number N of training data and the dimension D of the feature space, it either is advantageous to solve the primal problem or the dual problem.In this article, the case D >> N is discussed where D is so large that even a calculation of the dot product of fully occupied vectors in dimension D is too slow for the desired (e.g.real-time) application.Then a way to speed up the classification is to use an SVM which constructs a sparse linear classifier by solving an optimization problem involving the 1-norm, i.e. many components of the classifying vector are zero so that much less than D multiplications are neccessary to calculate the dot product.For a soft-margin SVM, in this article a theorem on the number of non-zero components is shown.