A Derandomized Sparse Johnson-Lindenstrauss Transform

Details A Derandomized Sparse Johnson-Lindenstrauss Transform A Derandomized Sparse Johnson-Lindenstrauss Transform

2010-06-18

arxiv.org/abs/1006.3585v3

Computer Science

Data Structures and Algorithms

v3: Improved seed length, alternative proof of JL row optimality, other minor changes; v2: Improved presentation. Added a warm

Scientific paper

Recent work of [Dasgupta-Kumar-Sarlos, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in our proof is improved. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, FOCS 2010].

Affiliated with

Also associated with

No associations

Rating

A Derandomized Sparse Johnson-Lindenstrauss Transform 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 A Derandomized Sparse Johnson-Lindenstrauss Transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Derandomized Sparse Johnson-Lindenstrauss Transform will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-259740