On the nonexistence of dimension reduction for $\ell2_2$ metrics.
Mohammad Moharrami, Avner Magen · Canadian Conference on Computational Geometry · 2008
An ‘ 2 metric is a metric such that p can be embedded isometrically into R d endowed with Euclidean norm, and the minimal possible d is the dimension associated with . A dimension reduction of an ‘ 2 metric is an embedding of into another ‘ 2 metric µ so that distances in µ are similar to those in and moreover, the dimension associated with µ is small. Much of the motivation in investigating dimension reductions in ‘ 2 comes from a result of Goemans which shows that if such metrics have good dimension reductions, then they embed well into ‘1 spaces. This in turn yields a rounding procedure to a host of semidefinite programming with good approximation guarantees. In this work we show that there is no dimension reduction ‘ 2 metrics in the following strong sense: for every function D(n) and for every n there exists an n point ‘ 2 metric such that for all embeddings of into an ‘ 2 metric µ with distortion at most D(n), the associated dimension of µ is at least n 1. This stands in striking contrast to the Johnson Lindenstrauss lemma which provides a logarithmic dimension reduction for ‘2 metrics.