
An \(\ell _p\) -sketch of \(x_i \in ^d\)  for computing \(O(1)\) -approximate \(\ell _p\) -distances which succeeds with probability \(1 - o(1/n^2)\)  [1]}. This sketch is used to compute distances between dataset points, as these are needed in order to compute the coreset of Corollary REF .

For each \(m \in [M]\)  and \(j \in [m]\) , we store the vector \(_j^{(m)} x_i \in ^s\) . This prepares the \(\ell _p^p\) -median sketch of Lemma REF  to be evaluated on a cluster of size \(m\) .

