There is one setting, of Euclidean space (\(p = 2\) ), where one can sketch vectors while preserving (). A sequence of works [1]}, [2]}, [3]}, [4]} show that applying a Johnson-Lindenstrauss [5]} map \(\colon ^d \rightarrow ^t\)  with \(t = O(z^4 \log (k/)/^2)\) , sketches Euclidean vectors to \(O(t \log (nd))\)  bits and preserves () up to \(1\pm \) . We emphasize that Euclidean space \(p = 2\)  is special in this regard, because the Johnson-Lindenstrauss map achieves dimension reduction, a property known not to hold in \(\ell _1\)  [6]}, [7]}, [8]}. In particular, \(d\) -dimensional vectors \(x \in ^d\)  in Euclidean space are sketched to vectors \((x) \in ^t\)  in Euclidean space, i.e., one estimates \(\Vert  x - y\Vert _2\)  by \(\Vert  (x) - (y)\Vert _2\) .
Thus the optimization problem () for \(d\) -dimensional Euclidean space reduces to the same optimization problem for a much smaller dimensional Euclidean space.
This can therefore be composed with known coreset constructions.
Importantly, the “sketched” space inherits all geometric properties of Euclidean spaces, a key aspect of prior works, and the reason they do not extend beyond Euclidean space.
The technical challenge in applying sketches for \(\ell _p\)  when \(p \ne 2\)  is that the “sketched” space is non-geometric.For example, the sketched space for \(\ell _p\)  with \(p \ne 2\)  does not satisfy the triangle inequality: it is not the case that for any \(x, y, z \in ^d\) , the estimate of \(((x), (y))\)  plus the estimate of \(((y), (z))\)  is less than the estimate of \(((x), (z))\) . On the other hand, for \(p = 2\) , the estimates of \(((x), (y))\) , \(((y), (z))\) , and \(((x), (z))\)  are \(\Vert  (x) - (y)\Vert _2\) , \(\Vert (y) - (z)\Vert _2\) , and \(\Vert (x) - (z)\Vert _2\) , so the triangle inequality does hold in the sketched space.
