Dimensionality reduction for k-means clustering and low rank approximation

DOI10.1145/2746539.2746569zbMATH Open1321.68398arXiv1410.6801OpenAlexW2133157266MaRDI QIDQ2941504FDOQ2941504

Authors: Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu 

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We show how to approximate a data matrix $mathbfA$ with a much smaller sketch $mathbfildeA$ that can be used to solve a general class of constrained k-rank approximation problems to within $(1+epsilon)$ error. Importantly, this class of problems includes $k$-means clustering and unconstrained low rank approximation (i.e. principal component analysis). By reducing data points to just $O(k)$ dimensions, our methods generically accelerate any exact, approximate, or heuristic algorithm for these ubiquitous problems. For $k$-means dimensionality reduction, we provide $(1+epsilon)$ relative error results for many common sketching techniques, including random row projection, column selection, and approximate SVD. For approximate principal component analysis, we give a simple alternative to known algorithms that has applications in the streaming setting. Additionally, we extend recent work on column-based matrix reconstruction, giving column subsets that not only `cover' a good subspace for $$, but can be used directly to compute this subspace. Finally, for $k$-means clustering, we show how to achieve a $(9+epsilon)$ approximation by Johnson-Lindenstrauss projecting data points to just $O(logk/epsilo{n}^2)$ dimensions. This gives the first result that leverages the specific structure of $k$-means to achieve dimension independent of input size and sublinear in $k$.

Full work available at URL: https://arxiv.org/abs/1410.6801

Recommendations

• Turning big data into tiny data: constant-size coresets for \(k\)-means, PCA and projective clustering
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Oblivious dimension reduction for \(k\)-means: beyond subspaces and the Johnson-Lindenstrauss lemma
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering

zbMATH Keywords

clusteringfeature selectionlow rank approximationprincipal component analysisdimensionality reductionsingular value decompositionsketching\(k\)-meansfeature extractiondistributedstreamingJohnson-Lindenstraussprojection cost preserving

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Shortest-path queries in static networks
• Approximate distance oracles
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On approximate distance labels and routing schemes with affine stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Approximate distance oracles with constant query time
• Fast C-K-R partitions of sparse graphs
• Automata, Languages and Programming
• Ramsey partitions and proximity data structures

Cited In (41)

• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• An efficient \(K\)-means clustering algorithm for tall data
• Title not available (Why is that?)
• Title not available (Why is that?)
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• Oblivious dimension reduction for \(k\)-means: beyond subspaces and the Johnson-Lindenstrauss lemma
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Turning big data into tiny data: constant-size coresets for \(k\)-means, PCA and projective clustering
• Low rank approximation of binary matrices: column subset selection and generalizations
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• Approximating spectral clustering via sampling: a review
• Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• A Doubly Enhanced EM Algorithm for Model-Based Tensor Clustering
• Efficient binary embedding of categorical data using BinSketch
• Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers
• \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
• Parameterized \(k\)-clustering: tractability island
• Frequent directions: simple and deterministic matrix sketching
• Sketching for principal component regression
• Online row sampling
• Robust communication-optimal distributed clustering algorithms
• Practical sketching algorithms for low-rank matrix approximation
• Infinite lattice learner: an ensemble for incremental learning
• Reduced-Rank Modeling for High-Dimensional Model-Based Clustering
• Title not available (Why is that?)
• An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
• Reduced \(k\)-means clustering with MCA in a low-dimensional space
• On coresets for support vector machines
• SketchySGD: reliable stochastic optimization via randomized curvature estimates
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Random projections for Bayesian regression
• Streaming low-rank matrix approximation with an application to scientific simulation
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Structural conditions for projection-cost preservation via randomized matrix multiplication
• Title not available (Why is that?)
• Exemplar-based low-rank matrix decomposition for data clustering
• A novel method for optimizing spectral rotation embedding \(K\)-means with coordinate descent
• Core-sets: updated survey

Uses Software

• Graphs

This page was built for publication: Dimensionality reduction for \(k\)-means clustering and low rank approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941504)