Oblivious Dimension Reduction for k-Means -- Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Lists
Only you see this
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...