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.
1 Comments:
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?
Post a Comment
<< Home