On the Exact Space Complexity of Sketching and Streaming Small Norms
Daniel M. Kane, Jelani Nelson, David P. Woodruff · 2010
We settle the 1-pass space complexity of \\((1 \\pm \\epsilon)\\)-approximating the \\(L_p\\) norm, for real p with 1 ≤ p ≤ 2, of a length-n vector updated in a length-m stream with updates to its coordinates. We assume the updates are integers in the range [–M, M]. In particular, we show the space required is \\(\\Theta(\\epsilon^{−2} log(mM) + log log(n))\\) bits. Our result also holds for 0 < p < 1; although \\(L_p\\) is not a norm in this case, it remains a well-defined function. Our upper bound improves upon previous algorithms of [Indyk, JACM ‘06] and [Li, SODA ‘08]. This improvement comes from showing an improved derandomization of the \\(L_p\\) sketch of Indyk by using k-wise independence for small k, as opposed to using the heavy hammer of a generic pseudorandom generator against space-bounded computation such as Nisan's PRG. Our lower bound improves upon previous work of [Alon-Matias-Szegedy, JCSS ‘99] and [Woodruff, SODA ‘04], and is based on showing a direct sum property for the 1-way communication of the gap-Hamming problem.