Saturday, August 18, 2007

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.


Anonymous Viagra Discount said...

interesting point of view, and your calculations are impressive, the way in your exposed this simple theorem make think, this could be apply to normal and simple vectorial calculation?

9:16 AM  

Post a Comment

<< Home