A lower bound on dimension reduction for trees in \ell_1

Abstract

There is a constant c > 0 such that for every $\epsilon \in (0,1)$ and $n\ge 1/{\epsilon }^2$, the following holds. Any mapping from the $n$-point star metric into ${\ell }_1^d$ with bi-Lipschitz distortion $1+\epsilon$ requires dimension $$d\ge \frac{c\log n}{{\epsilon }^2\log (1/\epsilon )}.$$

References in corpus (1)

• Entropy-based Bounds on Dimension Reduction in L_1