On the Sensitivity of Shape Fitting Problems
This work addresses computational geometry and machine learning problems for researchers, providing incremental improvements in coreset construction and sensitivity analysis.
The paper tackles shape fitting problems by deriving upper bounds for total sensitivities and constructing ε-coresets for various projective clustering variants, including k-median/k-means and j-subspace approximation, with extensions to high-dimensional cases.
In this article, we study shape fitting problems, $ε$-coresets, and total sensitivity. We focus on the $(j,k)$-projective clustering problems, including $k$-median/$k$-means, $k$-line clustering, $j$-subspace approximation, and the integer $(j,k)$-projective clustering problem. We derive upper bounds of total sensitivities for these problems, and obtain $ε$-coresets using these upper bounds. Using a dimension-reduction type argument, we are able to greatly simplify earlier results on total sensitivity for the $k$-median/$k$-means clustering problems, and obtain positively-weighted $ε$-coresets for several variants of the $(j,k)$-projective clustering problem. We also extend an earlier result on $ε$-coresets for the integer $(j,k)$-projective clustering problem in fixed dimension to the case of high dimension.