Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$

Details Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$ Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$

2004-07-30

arxiv.org/abs/math/0407520v1

Mathematics

Functional Analysis

3 pages. To appear in Geometric and Functional Analysis (GAFA)

Scientific paper

We show that any embedding of the level-k diamond graph of Newman and Rabinovich into $L_p$, $1 < p \le 2$, requires distortion at least $\sqrt{k(p-1) + 1}$. An immediate consequence is that there exist arbitrarily large n-point sets $X \subseteq L_1$ such that any D-embedding of X into $\ell_1^d$ requires $d \geq n^{\Omega(1/D^2)}$. This gives a simple proof of the recent result of Brinkman and Charikar which settles the long standing question of whether there is an $L_1$ analogue of the Johnson-Lindenstrauss dimension reduction lemma.

Affiliated with

Also associated with

No associations

Rating

Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-504042