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

DOI10.1145/3313276.3316318zbMath1433.68324OpenAlexW2951931394MaRDI QIDQ5212844

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

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

dimension reduction\(k\)-meansrandom projections

Mathematics Subject Classification ID

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

Related Items

A refined approximation for Euclidean \(k\)-means, Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections, Unnamed Item, Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering, 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