### 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