Dimensionality Reduction for k -Means and k -Medians Clustering

Speaker: 

Konstantin Makarychev, Associate Professor, Department of Computer Science, Northwestern University

Description: 

We investigate dimensionality reduction for Euclidean kk-means and kk-medians clustering. We show that the cost of the optimal solution for kk-means and kk-medians is preserved up to a factor of  (1+ε)(1+ε) under a projection onto a random  logklog⁡kdimensional subspace. Further, the cost of every clustering is preserved within  (1+ε)(1+ε) Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean kk-clustering with the distances raised to the pp-th power for any constant pp. Joint work with Yury Makarychev and Ilya Razenshteyn.

Event Topic

Mathematical Finance, Stochastic Analysis, and Machine Learning