2015/10/28 by Xu Wang, Gilad Lerman, Wang, Xu +1 · 1 citation
Computer Science · Engineering · #Advanced Clustering Algorithms Research #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1510.08406
openalex publication_date 2015/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Kernel methods obtain superb performance in terms of accuracy for various machine learning tasks since they can effectively extract nonlinear relations. However, their time complexity can be rather large especially for clustering tasks. In this paper we define a general class of kernels that can be easily approximated by randomization. These kernels appear in various applications, in particular, traditional spectral clustering, landmark-based spectral clustering and landmark-based subspace clustering. We show that for n data points from K clusters with D landmarks, the randomization procedure results in an algorithm of complexity O(KnD). Furthermore, we bound the error between the original clustering scheme and its randomization. To illustrate the power of this framework, we propose a new fast landmark subspace (FLS) clustering algorithm. Experiments over synthetic and real datasets demonstrate the superior performance of FLS in accelerating subspace clustering with marginal sacrifice of accuracy.