Axis-Aligned Projective Clustering

We study axis-aligned $(j,k,z)$-projective clustering of $n$ points in ${\mathbb{R}}^d$, where the objective sums the $z$th powers of Euclidean distances to the nearest of $k$ axis-aligned $j$-dimensional affine subspaces. For $j,k\ge 2$ and every constant $z\ge 1$, we obtain total-sensitivity bounds of $$\begin{gathered} (j+k{)}^{O_z(\min \\ j,k \\ )}\log n \end{gathered}$$, independent of the ambient dimension and requiring no bounds on input coordinates. Sensitivity sampling then yields small weighted coresets, with ambient dimension entering only through the complexity of the query family. Complementary lower bounds show that logarithmic dependence on $n$ and exponential dependence on $\min \{j,k\}$ are unavoidable, already in ${\mathbb{R}}^{j+1}$. We also establish ${\tilde{O}}_z(\sqrt{kj/n})$ expected excess-risk bounds on the unit sphere for linear subspaces and affine subspaces within unit distance of the origin. This bound is optimal up to logarithmic factors for the linear class when $d\ge 2kj$ and $n$ is sufficiently large relative to $kj$.