  Given $n$ points in $\ell_p^d$, we consider the problem of partitioning
points into $k$ clusters with associated centers. The cost of a clustering is
the sum of $p^{\text{th}}$ powers of distances of points to their cluster
centers. For $p \in [1,2]$, we design sketches of size
poly$(\log(nd),k,1/\epsilon)$ such that the cost of the optimal clustering can
be estimated to within factor $1+\epsilon$, despite the fact that the
compressed representation does not contain enough information to recover the
cluster centers or the partition into clusters. This leads to a streaming
algorithm for estimating the clustering cost with space
poly$(\log(nd),k,1/\epsilon)$. We also obtain a distributed memory algorithm,
where the $n$ points are arbitrarily partitioned amongst $m$ machines, each of
which sends information to a central party who then computes an approximation
of the clustering cost. Prior to this work, no such streaming or
distributed-memory algorithm was known with sublinear dependence on $d$ for $p
\in [1,2)$.
