Wednesday, April 10, 2019 - 12:00pm to 1:00pm
Location:4305 Newell-Simon Hall
Speaker:DAVID WOODRUFF, Associate Professor http://www.cs.cmu.edu/~dwoodruf/
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
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