2011 | OriginalPaper | Buchkapitel
Almost Optimal Explicit Johnson-Lindenstrauss Families
verfasst von : Daniel Kane, Raghu Meka, Jelani Nelson
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms. Constructions of linear embeddings satisfying the Johnson-Lindenstrauss property necessarily involve randomness and much attention has been given to obtain explicit constructions minimizing the number of random bits used. In this work we give explicit constructions with an almost optimal use of randomness: For 0 <
ε
,
δ
< 1/2, we obtain explicit generators
G
:{0,1}
r
→ ℝ
s
×
d
for
s
=
O
(log(1/
δ
)/
ε
2
) such that for all
d
-dimensional vectors
w
of norm one,
$$ \Pr_{y \in_u \{0,1\}^r}[\, |\|G(y)w\|^2 -1| > \epsilon\,] \leq \delta,$$
with seed-length
$r = O\left(\log d + \log (1/\delta) \cdot \log\left(\frac{\log(1/\delta)}{\epsilon}\right)\right)$
. In particular, for
$\delta = 1/\mathop{{\rm poly}}(d)$
and fixed
ε
> 0, we obtain seed-length
O
((log
d
) (loglog
d
)). Previous constructions required Ω(log
2
d
) random bits to obtain polynomially small error.
We also give a new elementary proof of the optimality of the JL lemma showing a lower bound of Ω(log(1/
δ
)/
ε
2
) on the embedding dimension. Previously, Jayram and Woodruff [10] used communication complexity techniques to show a similar bound.