Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds

Abstract

Kernel $k$-means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear $k$-means clustering algorithm. However, kernel $k$-means clustering is computationally expensive when the non-linear feature map is high-dimensional and there are many input points. Kernel approximation, e.g., the Nyström method, has been applied in previous works to approximately solve kernel learning problems when both of the above conditions are present. This work analyzes the application of this paradigm to kernel $k$-means clustering, and shows that applying the linear $k$-means clustering algorithm to $\frac{k}{\epsilon }(1+o(1))$ features constructed using a so-called rank-restricted Nyström approximation results in cluster assignments that satisfy a $1+\epsilon$ approximation ratio in terms of the kernel $k$-means cost function, relative to the guarantee provided by the same algorithm without the use of the Nyström method. As part of the analysis, this work establishes a novel $1+\epsilon$ relative-error trace norm guarantee for low-rank approximation using the rank-restricted Nyström approximation. Empirical evaluations on the $8.1$ million instance MNIST8M dataset demonstrate the scalability and usefulness of kernel $k$-means clustering with Nyström approximation. This work argues that spectral clustering using Nyström approximation---a popular and computationally efficient, but theoretically unsound approach to non-linear clustering---should be replaced with the efficient and theoretically sound combination of kernel $k$-means clustering with Nyström approximation. The superior performance of the latter approach is empirically verified.

References in corpus (5)

• Random Projections for $k$-means Clustering
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• Low Rank Approximation and Regression in Input Sparsity Time
• Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression

Cited by in corpus (22)

• Quantum Spectral Clustering
• Ultra-Fast Accurate AoA Estimation via Automotive Massive-MIMO Radar
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Efficient Data-Driven Geologic Feature Detection from Pre-stack Seismic Measurements using Randomized Machine-Learning Algorithm
• Kernel k-Means, By All Means: Algorithms and Strong Consistency
• Communication-Efficient Distributed SVD via Local Power Iterations
• Scalable Kernel Logistic Regression with Nyström Approximation: Theoretical Analysis and Application to Discrete Choice Modelling
• Perturbations of CUR Decompositions
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
• Fast Kernel k-means Clustering Using Incomplete Cholesky Factorization
• On the optimality of kernels for high-dimensional clustering
• Modern Subsampling Methods for Large-Scale Least Squares Regression
• Dissimilarity Mixture Autoencoder for Deep Clustering
• Nearly Optimal Clustering Risk Bounds for Kernel K-Means
• The GaussianSketch for Almost Relative Error Kernel Distance
• Gaussian Sketching yields a J-L Lemma in RKHS
• Coresets for Kernel Clustering
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• Improving classification performance by feature space transformations and model selection
• On Generalization Bounds for Projective Clustering
• Geometric Interpretation of Running Nyström-Based Kernel Machines and Error Analysis