Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension

Monday, February 25, 2019 - 1:25pm - 2:25pm
Lind 305
David Woodruff (Carnegie Mellon University)
We obtain the first strong coresets for the k-median and subspace approximation problems with sum of distances objective function, on n points in d dimensions, with a number of weighted points that is independent of both n and d; namely our coresets have size poly(k/eps). A strong coreset (1+eps)-approximates the cost function for all possible sets of centers simultaneously. We also give input sparsity time algorithms for computing these coresets, which are fixed parameter tractable in k/eps. We obtain the result by introducing a new dimensionality reduction technique for coresets that significantly generalizes earlier results for squared Euclidean distances to sums of p-th powers of Euclidean distances for constant p >= 1.

Joint work with Christian Sohler