Yury Makarychev : Dimensionality reduction for k-means and k-medians clustering

Posted by Will Perkins , part of the Computer Science Theory Seminar.

At

Dec. 4, 2019, 4:15 p.m.

In

1325 SEO

Abstract

Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+ε) under a projection onto a random O(log(k/ε)/ε^2)-dimensional subspace. Further, the cost of every clustering is preserved within (1+ε). More generally, our result applies to any dimensionality reduction satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p. Based on a joint work with Konstantin Makarychev and Ilya Razenshteyn.