whose value satisfies

x, jpj1/p (j'=1d x, j'ppj' )1/p, 

and is the largest among those heavy hitters. For the coordinate \(\in [d]\)  recovered by the \(\ell _p\) -sampling sketch [1]}, the inequality (REF ) gives a lower bound on how large \(1/_{}^{1/p}\)  will be. In particular, by applying the same transformation to the vector of sketches,

((x, 1)11/p,..., (x, d)d1/p ) (t)d       and      ('([1])11/p, ..., '([d])d1/p ) (t')d, 

the \(t\)  and \(t^{\prime }\)  coordinates corresponding to the sketches \((x_{\cdot , }) \in ^t\)  and \(^{\prime }(\Pr _{}[]) \in ^{t^{\prime }}\)  will be heavy hitters of those vectors as well. 
Namely, with only \((\log (nd), 1/)\) -bits, the Count-Min data structure will recover the entries of \((x_{\cdot , })\)  and \(^{\prime }(\Pr _{}[])\)  up to a small additive error, proportional to the \(\ell _1\) -norm of (REF ). We know the distribution of sketched vectors (REF ) (since these are simply \(\ell _p\) -sketches [2]}), so we will be able to bound the additive error and show that the sketch evaluation algorithms of \(\widehat{_1}\)  and \(\widehat{_2}\)  return the desired \((1\pm )\) -approximations.
