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

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

shijun 6.5

michael kors outletlouis vuittonlouis vuittonjordan 4 retroralph lauren ukkate spadecoach factorty outletmichael kors uklouis vuitton handbagslouis vuitton outletadidas shoeschristian louboutin outletlouis vuittonray ban wayfarercoach outletjordan 13slouis vuitton outletpandara jewelrychristian louboutin salecoach outletrunning warehousemichael korsmichael kors outletray ban sunglassescoach outletadidas running shoeslouis vuittonmulberry bagstods salegucci outletcoach outletchristian louboutin shoeslouis vuitton outletconcord 11cheap jerseys wholesalecopy watchescheap oakleyskate spade totesfitflop outlethollister outletPost a Comment

<< Home