Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Details Almost Optimal Explicit Johnson-Lindenstrauss Transformations Almost Optimal Explicit Johnson-Lindenstrauss Transformations

2010-11-29

arxiv.org/abs/1011.6397v2

Computer Science

Data Structures and Algorithms

Updated references to prior work and minor formatting changes

Scientific paper

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 n dimensions to O(log(1/delta)/epsilon^2) dimensions with error probability at most delta, and distortion at most epsilon. In particular, for delta = 1/poly(n) and fixed epsilon, we use O(log n loglog n) random bits. Previous constructions required at least O(log^2 n) random bits to get polynomially small error.

Affiliated with

Also associated with

No associations

Rating

Almost Optimal Explicit Johnson-Lindenstrauss Transformations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Almost Optimal Explicit Johnson-Lindenstrauss Transformations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost Optimal Explicit Johnson-Lindenstrauss Transformations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444235