# Dimensionality Reduction for $$k$$-Means and $$k$$-Medians Clustering

## When:

Nov 19, 2019 - 11:25am to 12:30pm

RE 119

## Speaker:

Konstantin Makarychev, Associate Professor, 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+\varepsilon)$$ under a projection onto a random  $$\log k$$dimensional subspace. Further, the cost of every clustering is preserved within  $$(1+\varepsilon)$$ 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$$. Joint work with Yury Makarychev and Ilya Razenshteyn.

## Event Type:

Department of Applied Mathematics - Mathematical Finance and Stochastic Analysis Seminar