Aarhus University Seal

Oblivious dimension reduction for k-means: Beyond subspaces and the Johnson-lindenstrauss lemma

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review


  • 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 languageEnglish
JournalProceedings of the Annual ACM Symposium on Theory of Computing
Pages (from-to)1039-1050
Number of pages12
Publication statusPublished - 23 Jun 2019
Externally publishedYes
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: 23 Jun 201926 Jun 2019


Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
CountryUnited States

Bibliographical note

Publisher Copyright:
© 2019 Association for Computing Machinery.

Copyright 2019 Elsevier B.V., All rights reserved.

    Research areas

  • Dimension reduction, K-means, Random projections

See relations at Aarhus University Citationformats

ID: 207579747