An efficient algorithm for solving linearized SVM regression problems

Support vector machines (SVMs) for regression are most commonly formulated as quadratic optimization problems (QP), and can be solved by several specialized algorithms, which need time and memory resources of the order of m 2 . J. Weston at al. [Support vector density estimation, In Advances in Kernel Methods-Support Vector Learning, B. Schölkopf, C. J. C. Burges, and A. J. Smola (eds.), MIT Press, Cambridge, MA, US, 293–306 (1999)] suggested that this problem could be reduced to a linear programming problem by adopting a linearized regularization term. Although the standard simlex approach can be applied to solve it, it would be very desirable to have a purpose-built algorithm. In this paper, we present an algorithm which exploits the special features of such linearized SVM problems and solves them in a very efficient way. The savings on both computational effort and storage requirement are significant, and are illustrated by several sets of experimental results.