Fast and convergence-guaranteed algorithm for linear separation

Abstract

Efficient linear separation algorithms are important for pattern classification applications. In this paper, an algorithm is developed to solve linear separation problems in n-dimensional space. Its convergence feature is proved. The proposed algorithm is proved to converge to a correct solution whenever the two sets are separable. The complexity of the proposed algorithm is analyzed, and experiments on both randomly generated examples and real application problems were carried out. While analysis shows that its time complexity is lower than SVM that needs computations for quadratic programming optimization, experiment results show that the developed algorithm is more efficient than the least-mean-square (LMS), and the Perceptron.