We show that fornpoints ind-dimensional Euclidean space, a dataoblivious random projection of the columns ontoO(((logk+log logn)/ε^6)log(1/ε)) dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1±ε) factor. The previous-bestupper bounds on O(logn/ε^2) given by a direct application of the Johnson-Lindenstrauss Lemma, and O(k/ε^2)given by [Cohen etal.-STOC’15]
Dettaglio pubblicazione
2019, STOC '19 51st Annual ACM SIGACT Symposium on the Theory of Computing, Pages 1039-1050
Oblivious Dimension Reduction fork-Means:Beyond Subspaces and the Johnson-Lindenstrauss Lemma (04b Atto di convegno in volume)
Becchetti Luca, Bury Marc, Cohen-Addad Vincent, Grandoni Fabrizio, Schwiegelshohn Chris Rene
ISBN: 978-1-4503-6705-9
Gruppo di ricerca: Algorithms and Data Science
keywords