A lower bound on dimension reduction for trees in \ell₁

Publication date: 26 February 2013

Abstract: There is a constant c > 0 such that for every

e p s i l o n i n (0, 1)

and

n g e q 1 / e p s i l o n^{2}

, the following holds. Any mapping from the

n

-point star metric into

e l l_{1}^{d}

with bi-Lipschitz distortion

1 + e p s i l o n

requires dimension

d geq {clog nover epsilon^2log (1/epsilon)}.

This page was built for publication: A lower bound on dimension reduction for trees in \ell_1