Nystrom method and low-rank linearized Support Vector Machines (SVMs) are two widely used methods for scaling up kernel SVMs, both of which need to sample part of columns of the kernel matrix to reduce the size. However, existing non-uniform sampling methods suf- fer from at least quadratic time complexity in the number of training data, limiting the scalability of kernel SVMs. In this paper, we pro- pose a parallel sampling method called parallel column subset selection (PCSS) based on the divide-and-conquer strategy, which divides the ker- nel matrix into several small submatrices and then selects columns in par- allel. We prove that PCSS has a (1+� ) relative-error upper bound with respect to the kernel matrix. Further, we present two approaches to scal- ing up kernel SVMs by combining PCSS with Nystrom method and low- rank linearized SVMs. The results of comparison experiments demon- strate the effectiveness, efficiency and scalability of our approaches.
['Jiangang Wu', 'Chang Feng', 'Peihuan Gao', 'Shizhong Liao']
Parallel Column Subset Selection of Kernel Matrix for Scaling up Support Vector Machines