Johnson-Lindenstrauss, updated

Jiri Matousek has a nice writeup with a variant of JL that I find useful. In standard JL, generating a k X n matrix T of random, independent \pm 1 suffices to map n points in n dimensions to points in k dimensions and preserve Euclidean distances upto 1\pm \eps, where k is about 1/\eps^2 \log n. This results in a dense T, and the quest has been to sparsify it. Ailon and Chazelle made terrific progress, and Matousek has a version that is interesting. Generate T by picking each entry to be

• +q^{-1/2} with prob q/2,
  
• -q^{-1/2} with prob q/2 and
  
• 0 with prob 1-q.
  

Then one gets JL type approximation for transforming unit vectors x in n dimensions provided ||x||_\infty \le \alpha and q is roughly \alpha^2 \log n. The key is that q controls the sparsity of T and so there is a tradeoff between the L_\infty norm of the vectors and the sparsity.