Dimensionality Reduction for -/k(/)Means and /k(/)-Medians Clustering
Speaker:
Konstantin Makarychev
Department of Computer Science, Northwestern University
Description:
We investigate dimensionality reduction for Euclidean /k(/)-means and /k(/)-medians clustering. We show that the cost of the optimal solution for k-means and k-medians is preserved up to a factor of (1+ε) under a projection onto a random /\log k(/)-dimensional subspace. Further, the cost of every clustering is preserved within (1+ε) Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean /k(/)-clustering with the distances raised to the -th power for any constant /p(/). Joint work with Yury Makarychev and Ilya Razenshteyn.
Event Topic
Mathematical Finance, Stochastic Analysis, and Machine Learning