  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$-dimensional flats such that $(\sum_{p\in
P}d(p, \mathcal{F})^\rho)^{1/\rho}$ is minimized; here $d(p, \mathcal{F})$
represents the (Euclidean) distance of $p$ to the closest flat in
$\mathcal{F}$. We let $f_k^q(P,\rho)$ denote the minimal value and interpret
$f_k^q(P,\infty)$ to be $\max_{r\in P}d(r, \mathcal{F})$. When $\rho=1,2$ and
$\infty$ and $q=0$, the problem corresponds to the $k$-median, $k$-mean and the
$k$-center clustering problems respectively.
  For every $0 < \epsilon < 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/\epsilon)/\epsilon^3) \log n)$ will $\epsilon$-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)$ dimensional randomly chosen subspace
$\epsilon$-approximates projective clusterings for every $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 $\epsilon$-approximate
projective clustering for every $k$ and $\rho$ simultaneously using only
$O((n+d)((q+1)^2\log ((q+1)/\epsilon))/\epsilon^3 \log n)$ space. Compared to
standard streaming algorithms with $\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.
