New Coresets for Projective Clustering and Applications
This work addresses computational efficiency in high-dimensional clustering and regression for data science applications, representing a novel advancement rather than an incremental improvement.
The paper tackles the problem of projective clustering by proposing the first algorithm that returns an L∞ coreset of polynomial size in dimension d, and introduces the first strong coreset construction for general M-estimator regression, covering various loss functions like Cauchy and Huber.
$(j,k)$-projective clustering is the natural generalization of the family of $k$-clustering and $j$-subspace clustering problems. Given a set of points $P$ in $\mathbb{R}^d$, the goal is to find $k$ flats of dimension $j$, i.e., affine subspaces, that best fit $P$ under a given distance measure. In this paper, we propose the first algorithm that returns an $L_\infty$ coreset of size polynomial in $d$. Moreover, we give the first strong coreset construction for general $M$-estimator regression. Specifically, we show that our construction provides efficient coreset constructions for Cauchy, Welsch, Huber, Geman-McClure, Tukey, $L_1-L_2$, 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.