KMA-α: A kernel matrix approximation algorithm for support vector machines

The computation of kernel matrices is essential for solving the support vector machines (SVM). Since the previous accurate approach is hard to apply in large-scale problems, there has been a lot deal of recent interests in the approximate approach, and a new approximation algorithm for the computation of kernel matrices is proposed in this paper. Firstly, we reformulate the quadratic optimization for SVM and multiple kernel SVM as a second-order cone programming (SOCP) through the convex quadratically constrained linear programming (QCLP). Then, we synthesize the Monte Carlo approximation and the incomplete Cholesky factorization, and present a new kernel matrix approximation algorithm KMA-α. KMA-α uses the Monte Carlo algorithm to randomly sample the kernel matrix. Rather than directly calculate the singular value decomposition of the sample matrix, KMA-α applies the incomplete Cholesky factorization with symmetric permutation to obtain the near-optimal low rank approximation of the sample matrix. The approximate matrix produced by KMA-α can be used in SOCP to improve the efficiency of SVM. Further, we analyze the computational complexity and prove the error bound theorem about the KMA-α algorithm. Finally, by the comparative experiments on benchmark datasets, we verify the validity and the efficiency of KMA-α. Theoretical and experimental results show that KMA-α is a valid and efficient kernel matrix approximation algorithm.