Oblivious Dimension Reduction for k-Means -- Beyond Subspaces and the Johnson-Lindenstrauss Lemma

Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, Chris SchwiegelshohnZenodo 2020 · DOI · OpenAlex

Abstract

We show that for n points in d-dimensional Euclidean space, a data oblivious random projection of the columns onto \(m \in O(\frac{(\log k+\log \log n)\log 1/\varepsilon)}{\varepsilon^6}) \) dimensions is suffcient to approximate the cost of all k-means clusterings up to a multiplicative \((1\pm \varepsilon)\)factor. The previous-best upper bounds on m are \(O(\varepsilon^{-2}\log n)\) given by a direct application of the Johnson-Lindenstrauss<br> Lemma, and \(O(k\varepsilon^{-2})\) given by [Cohen et al.-STOC'15].<br> We also prove the existence of a non-oblivious cost preserving sketch with target dimension \(O(\frac{(\log k+\log \log n)\log 1/\varepsilon)}{\varepsilon^4}) \), improving on \(\lceil\frac{k}{\varepsilon}\rceil\) [Cohen et al.-STOC'15]. Furthermore, we show how to construct strong coresets for the k-means problem of size \(O(k\cdot\text{poly}(\log k,\varepsilon^{-1}))\). Previous constructions of strong coresets have size of order \(k\cdot \min(d,k/\varepsilon)\).
BibTeX
@inproceedings{becchetti2020oblivious,
  author = {Luca Becchetti and Marc Bury and Vincent Cohen-Addad and Fabrizio Grandoni and Chris Schwiegelshohn},
  title = {{Oblivious Dimension Reduction for k-Means -- Beyond Subspaces and the Johnson-Lindenstrauss Lemma}},
  booktitle = {Zenodo},
  year = {2020},
  doi = {10.5281/zenodo.4586891},
}

Loading related content...

Figure