L1 norm discrimination consists in finding the hyperplane that minimizes the sum of L1 norm distances between the hyperplane and the points that lie on the wrong side of the hyperplane. This problem is difficult for datasets containing more than 100,000 points. Since few points are needed to obtain the optimal hyperplane, we propose a point selection algorithm which iteratively adds the necessary points to a re- duce set of points. We evaluate different point selection criteria. The resulting method obtains in reasonable times exact solutions for problems of up to two million points.
Published August 2005 , 15 pages