Approximation and Streaming Algorithms for Projective Clustering via Random Projections

Michael Kerber, Sharath Raghvendra

Let $P$ be a set of $n$ points in ${\mathbb{R}}^d$. In the projective clustering problem, given $k,q$ and norm $\rho \in [1,\infty ]$, we have to compute a set $\mathcal{F}$ of $k$ $q$-d…