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  
Blogger Shijun Lin said...

shijun 6.5
michael kors outlet
louis vuitton
louis vuitton
jordan 4 retro
ralph lauren uk
kate spade
coach factorty outlet
michael kors uk
louis vuitton handbags
louis vuitton outlet
adidas shoes
christian louboutin outlet
louis vuitton
ray ban wayfarer
coach outlet
jordan 13s
louis vuitton outlet
pandara jewelry
christian louboutin sale
coach outlet
running warehouse
michael kors
michael kors outlet
ray ban sunglasses
coach outlet
adidas running shoes
louis vuitton
mulberry bags
tods sale
gucci outlet
coach outlet
christian louboutin shoes
louis vuitton outlet
concord 11
cheap jerseys wholesale
copy watches
cheap oakleys
kate spade totes
fitflop outlet
hollister outlet

7:21 PM  
Blogger 750unique said...

oakley sunglasses outlet
coach outlet store online
pandora charms
abercrombie kids
oakley outlet store
nike pas cher
oakley sunglasses sale
ralph lauren polo shirts
oakley sunglasses cheap
coach outlet
tory burch handbags
chanel handbags
cheap ray bans
coach factory outlet
true religion
pandora jewelry outlet
air force pas cher
ray ban glasses
louis vuitton borse
coach outlet
michael kors outlet
mont blanc pens
tory burch outlet online
cheap oakleys
cheap air max
michael kors
soccer outlet
hollister outlet
ed hardy uk
michael kors uk outlet
michael kors outlet online
gucci borse
mcm outlet online

3:00 AM  

Post a Comment

<< Home