Arbitrary-Norm Separating Plane

Abstract

A plane separating two point sets in n-dimensional real space is constructed such that it minimized the sum of arbitrary-norm distances of misclassified points to the plane. In contrast the previous approaches used surrogates to the misclassified-point distance-minimization problem, the present approach is based on a norm-dependent explicit closed form for the projection of a point on a plane. This projection is used to formulate the separating-plane problem as a minimization of a convex function on a unit sphere in a norm dual to that of the arbitrary norm used. For the 1-norm only, the problem can be solved in polynomial time by solving 2n linear programs or by soling a bilinear program. For all other p-norms, p E (1,infinity], a related decision problem to the minimization problem is NP-complete. For a general p-norm, the minimization problem can be transformed via an exact penalty formulation to minimizing the sum of a convex function and a bilinear function on a convex set. For the one and infinity norms, a finite successive linearization algorithm is proposed for solving the exact penalty formulation.