Kristian Woodsend and J. Gondzio
A parallel implementation of Support Vector Machine training for problems involving nonlinear kernels has been developed. The kernel matrix is approximated by a partial Cholesky decomposition. Theoretical issues associated with constructing the best possible (and yet computationally efficient) approximation are discussed in detail and implemented in OOPS. The structure of the augmented system matrix is exploited to partition data and computations amongst parallel processors efficiently. The new implementation has been applied to solve problems which involve very large data sets. Excellent parallel efficiency was observed on such problems.
Key words: Parallel support vector machines, Interior point method, Separable quadratic program, Low-rank approximation, Cholesky factorization