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