Daniel Hsu
|
8
|
 |
|
03-07-2007 01:29 PM ET (US)
|
|
Embedding l2 into l1
It seems that random projections should yield constant distortion embeddings from l2 into l1. As a crude estimate, if x is a unit vector in l2^D and A is a d-by-D matrix of Gaussian random variables, then in expectation, Ax/d has norm about 0.8. Large deviation bounds or concentration of measure (and d=O(log n)) can then do the rest as in the JL lemma.
Does this seem plausible? Using Dvorestsky's theorem would probably be of the same flavor, but might give a lower-dimension embedding.
|