New coresets for projective clustering and applications

摘要: -projective clustering is the natural generalization of the family of -clustering and -subspace clustering problems. Given a set of points in , the goal is to find flats of dimension , ie, affine subspaces, that best fit under a given distance measure. In this paper, we propose the first algorithm that returns an coreset of size polynomial in . Moreover, we give the first strong coreset construction for general -estimator regression. Specifically, we show that our construction provides efficient coreset constructions for Cauchy, Welsch, Huber, Geman-McClure, Tukey, , and Fair regression, as well as general concave and power-bounded loss functions. Finally, we provide experimental results based on real-world datasets, showing the efficacy of our approach.