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 ∈ (0, 2], one can maintain (using only O (log n /ϵ 2 ) words of storage) a sketch C(q) of a point q ∈ l n p under dynamic updates of its coordinates. The sketch has the property that, given C(q) and C(s) , one can estimate ‖ q − s ‖ p up to a factor of (1 + ϵ) 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 ∈ ℜ n and y ∈ ℜ m , estimates ‖ Ax − y ‖ p in O ( n + m ) time, for any p ∈ (0, 2]. This generalizes an earlier algorithm of Wasserman and Blum 1997 which worked for the case p = 2.---We obtain another sketch function C ′ which probabilistically embeds l n 1 into a normed space l m 1 . The embedding guarantees that, if we set m = log(1/δ) O (1/ϵ) , then for any pair of points q , s ∈ l n 1 , the distance between q and s does not increase by more than (1 + ϵ) with constant probability, and it does not decrease by more than (1 − ϵ) with probability 1 − δ. 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 n 2 into l n O (log n ) 1 with distortion (1 + 1/ n Θ(1) ).