Random Projections for k-means Clustering

2010/11/21 by Christos Boutsidis, Boutsidis, Christos, Anastasios Zouzias +3 · 81 citations
Computer Science · Engineering · Mathematics · #Algorithm #Artificial Intelligence (cs.AI) #Artificial intelligence #Cluster analysis #Combinatorics #Computer science #Constant (computer programming) #Data Structures and Algorithms (cs.DS) #Dimensionality reduction #Discrete mathematics #FOS: Computer and information sciences #Face and Expression Recognition #Geometry #Mathematics #Matrix (chemical analysis) #Partition (number theory) #Point (geometry) #Projection (relational algebra) #Random projection #Row #Set (abstract data type) #Sparse and Compressive Sensing Techniques #Statistics #Topological and Geometric Data Analysis #cs.AI #cs.DS #k-means clustering

paper · pdf · doi:10.48550/arxiv.1011.4632

published in arXiv (Cornell University) 23, 298-306 (Cornell University) · Neural Information Processing Systems (NIPS) 2010

arxiv created 2010/11/21 · openalex publication_date 2010/11/21 · arxiv updated 2011/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper discusses the topic of dimensionality reduction for k-means clustering. We prove that any set of n points in d dimensions (rows in a matrix A ∈ \RR^{n × d}) can be projected into t = Ω(k / \eps²) dimensions, for any \eps ∈ (0,1/3), in O(n d \lceil \eps^-2 k/ log(d) \rceil ) time, such that with constant probability the optimal k-partition of the point set is preserved within a factor of 2+\eps. The projection is done by post-multiplying A with a d × t random matrix R having entries +1/√(t) or -1/√(t) with equal probability. A numerical implementation of our technique and experiments on a large face images dataset verify the speed and the accuracy of our theoretical results.

Citations

• Database-friendly random projections: Johnson-Lindenstrauss with binary coins
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Least squares quantization in PCM

Cited by

• Dimension Reduction for Clustering: The Curious Case of Discrete Centers
• Simplicial clustering using the α--transformation
• Tensorized Random Projections
• Iterative Exploration-Driven Sparse SDP Clustering via Thompson Sampling
• Dimensionality Reduction for k-means Clustering

Related

• Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees
• Simple, Scalable and Effective Clustering via One-Dimensional Projections
• Dimensionality Reduction for k-means Clustering
• High-dimensional clustering via Random Projections
• The Bane of Low-Dimensionality Clustering