Stable distributions, pseudorandom generators, embeddings, and data stream computation

In this article, we show several results obtained by combining the use of stable distributions with pseudorandom generators for bounded space. In particular: We show that, for any p is an element of (0, 2], one can maintain (using only O (log n/epsilon(2)) words of storage) a sketch C (q) of a point q is an element of l(p)(n) under dynamic updates of its coordinates. The sketch has the property that, given C (q) and C(s), one can estimate parallel to q-s parallel to(p) up to a factor of (1+epsilon) with large probability. This solves the main open problem of Feigenbaum et al. [1999]. We show that the aforementioned sketching approach directly translates into an approximate algorithm that, for a fixed linear mapping A, and given x is an element of R-n and y is an element of R-m, estimates parallel to Ax-y parallel to(p) in O(n+m) time, for any p is an element of (0, 2]. This generalizes an earlier algorithm of Wasserman and Blum (19971 which worked for the case p=2. We obtain another sketch function C' which probabilistically embeds l(1)(n) into a normed space l(1)(m). The embedding guarantees that, if we set m=log(1/delta)(O(1/epsilon)), then for any pair of points q, s is an element of l(1)(n), the distance between q and s does not increase by more than (1+6 epsilon) with constant probability, and it does not decrease by more than (1-epsilon) with probability 1-delta. This is the only known dimensionality reduction theorem for the l(1) norm. In fact, stronger theorems of this type (i.e., that guarantee very low probability of expansion as well as of contraction) cannot exist [Brinkman and Charikar 2003]. We give an explicit embedding of l(2)(n) into with distortion (1+1/n(Theta(1))).