Kernel classification using a linear programming approach

A support vector machine (SVM) classifier corresponds in its most basic form to a quadratic programming problem. Various linear variations of support vector classification have been investigated such as minimizing the L-1-norm of the weight-vector instead of the L-2-norm. In this paper we introduce a classifier where we minimize the boundary (lower envelope) of the epigraph that is generated over a set of functions, which can be interpreted as a measure of distance or slack from the origin. The resulting classifier appears to provide a generalization performance similar to SVMs while displaying a more advantageous computational complexity. The discussed formulation can also be extended to allow for cases with imbalanced data.