2016/08/26 by Farhad Pourkamali-Anaraki, Stephen Becker, Pourkamali-Anaraki, Farhad +1
Mathematics · #FOS: Computer and information sciences #Machine Learning (stat.ML) #stat.ML
paper · pdf · doi:10.48550/arxiv.1608.07597
To appear in IEEE GlobalSIP 2016
arxiv created 2016/12/02 · arxiv updated 2016/12/05
Kernel-based K-means clustering has gained popularity due to its simplicity and the power of its implicit non-linear representation of the data. A dominant concern is the memory requirement since memory scales as the square of the number of data points. We provide a new analysis of a class of approximate kernel methods that have more modest memory requirements, and propose a specific one-pass randomized kernel approximation followed by standard K-means on the transformed data. The analysis and experiments suggest the method is accurate, while requiring drastically less memory than standard kernel K-means and significantly less memory than Nystrom based approximations.