Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma

DOI10.1145/3313276.3316318MaRDI QIDQ5212844zbMATH OpenOpenAlexFDO

Authors Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, Chris Schwiegelshohn

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3313276.3316318

zbMATH Keywords

\(k\)-meansdimension reductionrandom projections

Mathematics Subject Classification ID

Metric embeddings as related to computational problems and algorithms (68R12) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Dimensionality reduction for k-means clustering and low rank approximation
• On the Performance of Clustering in Hilbert Spaces
• Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering

Cited in

(14)

• A refined approximation for Euclidean \(k\)-means
• Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections
• Dimensionality reduction for k-means clustering and low rank approximation
• On the Performance of Clustering in Hilbert Spaces
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• scientific article; zbMATH DE number 7164768 (Why is no real title available?)
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• Distributed estimation and inference for spatial autoregression model with large scale networks
• Coresets for kernel clustering
• Moderate dimension reduction for k-center clustering
• Turning big data into tiny data: coresets for unsupervised learning problems
• An empirical evaluation of k-means coresets
• On coresets for fair clustering in metric and Euclidean spaces and their applications

This page was built for publication: Oblivious dimension reduction for \(k\)-means: beyond subspaces and the Johnson-Lindenstrauss lemma

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