Binary Classification via Ellipsoidal Separation

Separating two finite set of points in an Euclidean space is a fundamental problem in classification. Customarily linear separation is used, but nonlinear separators such as spheres [1] have been shown to be possible and to have superior performances in some tasks, such as edge detection in images. We exploit the relationships between the more general version of the latter separation, where we use general ellipsoids rather than spheres, with the SVM model with quadratic kernel to propose a classification approach. The implementation basically boils down to adding a SDP constraint to the standard SVM model in order to ensure that the chosen hyperplane in the feature space represents a non-degenerate ellipsoid in the input space; this may result in efficiency problems but still allows to exploit many of the techniques developed for SVR in combination with SDP approaches. We test our approach on several classification tasks, among which the edge detection problem for gray-scale images, proving that the approach is competitive with both the spherical classification one and the quadratic-kernel SVM one without the ellipsoidal restriction.