Large scale kernel regression via linear programming

The problem of tolerant data fitting by a nonlinear surface, induced by a k ernel-based support vector machine is formulated as a linear program with f ewer number of variables than that of other linear programming formulations . A generalization of the linear programming chunking algorithm for arbitra ry kernels is implemented for solving problems with very large datasets whe rein chunking is performed on both data points and problem variables. The p roposed approach tolerates a small error, which is adjusted parametrically, while fitting the given data. This leads to improved fitting of noisy data (over ordinary least error solutions) as demonstrated computationally. Com parative numerical results indicate an average time reduction as high as 26 .0% over other formulations, with a maximal time reduction of 79.7%. Additi onally, linear programs with as many as 16,000 data points and more than a billion nonzero matrix elements are solved.