Randomized Clustered Nystrom for Large-Scale Kernel Machines


  • Farhad Pourkamali-Anaraki University of Colorado Boulder
  • Stephen Becker University of Colorado Boulder
  • Michael Wakin Colorado School of Mines




kernel methods, low-rank approximation, Nystrom, feature extraction


The Nystrom method is a popular technique for generating low-rank approximations of kernel matrices that arise in many machine learning problems. The approximation quality of the Nystrom method depends crucially on the number of selected landmark points and the selection procedure. In this paper, we introduce a randomized algorithm for generating landmark points that is scalable to large high-dimensional data sets. The proposed method performs K-means clustering on low-dimensional random projections of a data set and thus leads to significant savings for high-dimensional data sets. Our theoretical results characterize the tradeoffs between accuracy and efficiency of the proposed method. Moreover, numerical experiments on classification and regression tasks demonstrate the superior performance and efficiency of our proposed method compared with existing approaches.




How to Cite

Pourkamali-Anaraki, F., Becker, S., & Wakin, M. (2018). Randomized Clustered Nystrom for Large-Scale Kernel Machines. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11614