Entropy-based Bounds on Dimension Reduction in L_1

Oded Regev

We show that for every large enough integer $N$, there exists an $N$-point subset of $L_1$ such that for every $D>1$, embedding it into ${\ell }_1^d$ with distortion $D$ requires dime…