Fast and convergence-guaranteed algorithm for linear separation

Zhi Yong Liu, Dapeng Zhang, Yu Gang Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

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.
Original languageEnglish
Pages (from-to)729-737
Number of pages9
JournalScience in China, Series F: Information Sciences
Volume53
Issue number4
DOIs
Publication statusPublished - 8 Feb 2010

Keywords

  • Classification
  • Complexity
  • Convergence
  • Efficiency
  • Linear separation problem

ASJC Scopus subject areas

  • Computer Science(all)

Cite this