At a high level, the \(\ell _p\) -sampling sketch of [1]} generates a sample \(\)  from \([d]\)  by identifying a heavy hitter in a random scaling of the vector specifying the sampling probabilities. In particular, the algorithm generates \(_1,\dots , _d \sim \mathrm {Exp}(1)\)  and identifies an entry \(j \in [d]\)  in the vector
\( \left( \frac{\Vert x_{\cdot , 1}\Vert _p}{_{1}^{1/p}}, \frac{\Vert x_{\cdot , 2}\Vert _p}{_{2}^{1/p}}, \dots , \frac{\Vert x_{\cdot , d-1}\Vert _p}{_{d-1}^{1/p}}, \frac{\Vert x_{\cdot , d}\Vert _p}{_{d}^{1/p}}\right) \in ^d,\) 
