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

Abstract

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 \(\text{poly}(k/\epsilon)\). A strong coreset \((1+\epsilon)\)-approximates the cost function for all possible sets of centers simultaneously. We also give efficient \(\text{nnz}(A) + (n+d)\text{poly}(k/\epsilon) + \exp(\text{poly}(k/\epsilon))\) time algorithms for computing these coresets. We obtain the result by introducing a new dimensionality reduction technique for coresets that significantly generalizes an earlier result of Feldman, Sohler and Schmidt \cite{FSS13} for squared Euclidean distances to sums of \(p\)-th powers of Euclidean distances for constant \(p\ge1\).