Approximation and Streaming Algorithms for Projective Clustering via Random Projections

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,\mathrm{\infty }]$, we have to compute a set $\mathcal{F}$ of $k$ $q$-dimensional flats such that $(\sum_{p\in P}d(p, $\mathcal{F}$)^\rho)^{1/\rho}$isminimized;here$d(p, $\mathcal{F}$)$representsthe(Euclidean)distanceof$p$totheclosestflatin$$\mathcal{F}$$\mathrm{.}Welet$f_k^q(P,\rho)$denotetheminimalvalueandinterpret$f_k^q(P,\infty)$tobe$\max_{r\in P}d(r, $\mathcal{F}$)$\mathrm{.}When$\rho=1,2$and$\infty$and$q=0$,theproblemcorrespondstothe$k$-median,$k$-meanandthe$k$-center clustering problems respectively. For every $0<ϵ<1$, $S\subset P$ and $\rho \ge 1$, we show that the orthogonal projection of $P$ onto a randomly chosen flat of dimension $O(((q+1{)}^2\log (1\mathrm{/}ϵ)\mathrm{/}{ϵ}^3)\log n)$ will $ϵ$-approximate $f_1^q(S,\rho )$. This result combines the concepts of geometric coresets and subspace embeddings based on the Johnson-Lindenstrauss Lemma. As a consequence, an orthogonal projection of $P$ to an $O(((q+1)^2 \log ((q+1)/\epsilon)/\epsilon^3) \log n)$dimensionalrandomlychosensubspace$\epsilon$-approximatesprojectiveclusteringsforevery$k$and$\rho$ simultaneously. Note that the dimension of this subspace is independent of the number of clusters~$k$. Using this dimension reduction result, we obtain new approximation and streaming algorithms for projective clustering problems. For example, given a stream of $n$ points, we show how to compute an $ϵ$-approximate projective clustering for every $k$ and $\rho$ simultaneously using only $O((n+d)((q+1{)}^2\log ((q+1)\mathrm{/}ϵ))\mathrm{/}{ϵ}^3\log n)$ space. Compared to standard streaming algorithms with $\mathrm{\Omega }(kd)$ space requirement, our approach is a significant improvement when the number of input points and their dimensions are of the same order of magnitude.