In addition to constructing coresets, an algorithm may seek to optimize the dependence on \(d\) .
There is a large body of work studying (oblivious) dimensionality reduction and sketching, where strong compression results are known for computing distances [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}, [13]}. For example, for \(p \in [1,2]\)  there exists a (randomized) sketch \(\colon ^d \rightarrow ^t\)  with \(t\)  much smaller than \(d\)  such that, for any two vectors \(x, y \in ^d\) , an algorithm can approximate \(\Vert  x -y\Vert _p\)  from \((x)\)  and \((y)\)  with high probability. While these results are encouraging, leveraging such sketches for distance computation in order to compress entire optimization problems like () is highly nontrivial.
The challenge is that () implicitly considers distances among infinitely many vectors, and we need to rule out the possibility of spurious low cost solutions in the “sketched” space which do not have an analog in the original space. In particular, prior to this work, no streaming or distributed-memory algorithm was known which could reduce the dependence on \(d\)  for \(p \in [1, 2)\) .
