Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-183 | 5th October 2011 23:30

Almost Optimal Explicit Johnson-Lindenstrauss Transformations

RSS-Feed

Abstract:

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. In particular, for the important case of polynomially small error and constant distortion, we give a generator with seed-length O((log d)(log log d)). Previous constructions required $\Omega(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 $\Omega(\log(1/\delta)/\epsilon^2)$ on the
embedding dimension. Previously, Jayram and Woodruff [JW11] used communication complexity techniques to show a similar
bound.



Changes to previous version:

Merger of two works - has two different constructions. Fixes a mistake in the use of samplers from previous version.


Revision #1 to TR10-183 | 2nd February 2011 18:47

Almost Optimal Explicit Johnson-Lindenstrauss Transformations





Revision #1
Authors: Raghu Meka
Accepted on: 2nd February 2011 18:47
Downloads: 2747
Keywords: 


Abstract:

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction with an almost optimal use of randomness: we use $O(\log(n/\delta) \log(\log(n/\delta)/\epsilon))$ random bits for embedding $\ell_2^n$ into $\ell_2^s$ with error probability $\delta$, and distortion at most $\epsilon$, where $s = O(\log(1/\delta)/\epsilon^2)$.

In particular, for $\delta = 1/poly(n)$ and fixed $\epsilon > 0$, our construction uses $O(\log n \log \log n)$ random bits. Previous constructions required at least $O(\log^2 n)$ random bits to get polynomially small error.


Paper:

TR10-183 | 29th November 2010 22:37

Almost Optimal Explicit Johnson-Lindenstrauss Transformations





TR10-183
Authors: Raghu Meka
Publication: 29th November 2010 23:16
Downloads: 3147
Keywords: 


Abstract:

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction with an almost optimal use of randomness: we use $O(\log(n/\delta) \log(\log(n/\delta)/\epsilon))$ random bits for embedding $\ell_2^n$ into $\ell_2^s$ with error probability $\delta$, and distortion at most $\epsilon$, where $s = O(\log(1/\delta)/\epsilon^2)$.

In particular, for $\delta = 1/poly(n)$ and fixed $\epsilon > 0$, our construction uses $O(\log n \log \log n)$ random bits. Previous constructions required at least $O(\log^2 n)$ random bits to get polynomially small error.



ISSN 1433-8092 | Imprint