Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering

DOI10.1145/3313276.3316350zbMath1433.68366arXiv1811.03195OpenAlexW2962777529MaRDI QIDQ5212843

Yury Makarychev, Konstantin Makarychev, Ilya Razenshteyn

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://arxiv.org/abs/1811.03195

zbMATH Keywords

clusteringdimension reductionk-meansJohnson-Lindenstrauss transformKirszbraun theoremk-medians

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Metric embeddings as related to computational problems and algorithms (68R12)

Related Items (10)

A refined approximation for Euclidean \(k\)-means ⋮ An improved primal-dual approximation algorithm for the k-means problem with penalties ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument ⋮ Dimension reduction for maximum matchings and the fastest mixing Markov chain ⋮ k-means-g*: accelerating \(k\)-means clustering algorithm utilizing primitive geometric concepts ⋮ Fast Metric Embedding into the Hamming Cube ⋮ Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ On coresets for support vector machines

This page was built for publication: Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering