High frequency moments via max-stability
Abstract
We present anew, simple algorithm for sketching the k > 2 frequency moment of a dynamic stream, or simply the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> norm of a vector in the linear sketching model. The new algorithms are based on exponentially distributed random variables, which possess a certain “max-stability” property, similar in spirit to the “p-stability” property used in [Indyk, JACM'06] for sketching ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> norms for k ≤ 2. Our resulting sketching algorithm can be seen as a “weak embedding” of an n-dimensional ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> space into 1 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> space of dimension m = O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-2/k</sup> log n): it preserves the norm of a vector up to constant approximation, with constant probability. We note that this dimension is optimal for linear embeddings (sketches) with constant approximation, as shown in [Andoni-Nguyen-Polyanskiy-Wu, ICALP'13]. The preliminary version of this result has appeared as a blog post in 2012, and its main idea has since been used in other streaming algorithms.
BibTeX
@inproceedings{icassp2017_highfrequencymom,
title = {High frequency moments via max-stability},
author = {Alexandr Andoni},
booktitle = {ICASSP 2017},
year = {2017}
}