About Aarhus University
Oblivious dimension reduction for k-means: Beyond subspaces and the Johnson-lindenstrauss lemma
Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Conference article › Research › peer-review
DOI
- https://doi.org/10.1145/3313276.3316318
Final published version
- Luca Becchetti, University of Rome La Sapienza ,
- Marc Bury, Zalando SE ,
- Vincent Cohen-Addad, CNRS ,
- Fabrizio Grandoni, Universita della Svizzera italiana ,
- Chris Schwiegelshohn
We show that for n points in d-dimensional Euclidean space, a data oblivious random projection of the columns ontom ∈ O log k+log log n log ε1 ε6 dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1 ± ε) factor. The previous-best upper bounds on m are O(logε2n ) given by a direct application of the Johnson-Lindenstrauss Lemma, and O(εk2 ) given by [Cohen et al.-STOC’15].
| Original language | English |
|---|---|
| Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
| Pages (from-to) | 1039-1050 |
| Number of pages | 12 |
| ISSN | 0737-8017 |
| DOIs | |
| Publication status | Published - 23 Jun 2019 |
| Externally published | Yes |
| Event | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States Duration: 23 Jun 2019 → 26 Jun 2019 |
Conference
| Conference | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 |
|---|---|
| Country | United States |
| City | Phoenix |
| Period | 23/06/2019 → 26/06/2019 |
| Sponsor | ACM SIGACT |
Bibliographical note
Publisher Copyright:
© 2019 Association for Computing Machinery.
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
- Dimension reduction, K-means, Random projections
Research areas
See relations at Aarhus University Citationformats
ID: 207579747