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

Access Restriction
Subscribed

 Author Indyk, Piotr Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2006 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Data streams ♦ Dimensionality reduction ♦ Embeddings ♦ Norms ♦ Sketching Abstract 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 $\textit{p}$ ∈ (0, 2], one can maintain (using only $\textit{O}(log$ $n/ε^{2})$ words of storage) a $\textit{sketch}$ $\textit{C(q)}$ of a point $\textit{q}$ ∈ $l^{n}_{p}$ under dynamic updates of its coordinates. The sketch has the property that, given $\textit{C(q)}$ and $\textit{C(s)},$ one can estimate $‖\textit{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 $\textit{A},$ and given $\textit{x}$ ∈ $ℜ^{n}$ and $\textit{y}$ ∈ $ℜ^{m},$ estimates $‖\textit{Ax}$ ™ $y‖_{p}$ in $\textit{O}(\textit{n}$ + $\textit{m})$ time, for any $\textit{p}$ ∈ (0, 2]. This generalizes an earlier algorithm of Wasserman and Blum [1997] which worked for the case $\textit{p}$ = 2.---We obtain another sketch function $\textit{C}′$ which probabilistically embeds $l^{n}_{1}$ into a normed space $l^{m}_{1}.$ The embedding guarantees that, if we set $\textit{m}$ = $log(1/Δ)^{O(1/ε)},$ then for any pair of points $\textit{q},$ $\textit{s}$ ∈ $l^{n}_{1},$ the distance between $\textit{q}$ and $\textit{s}$ does not $\textit{increase}$ by more than (1 + ε) with constant probability, and it does not $\textit{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 $\textit{l}\textit{n}\textit{O}(log$ $n)}}_{1}$ with distortion (1 + $1/n^{Θ(1)}).$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2006-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 53 Issue Number 3 Page Count 17 Starting Page 307 Ending Page 323

#### Open content in new tab

Source: ACM Digital Library