Access Restriction

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

   Open content in new tab
Source: ACM Digital Library