Low Distortion Metric Embedding into Constant Dimension

摘要

We investigate the possibility of embedding an n-point met ric space into a constant dimensional vector space with the maximum norm, such that the embedding is almost isometric, that is, the distor tion of distances is kept arbitrarily close to 1. When the source metric is generated by any fixed norm on a finite dimensional vector space, we prove that this embedding is always possible, such that the dimension of the target space remains constant, independent of n. While this possi bility has been known in the folklore, we present the first fully detailed proof, which, in addition, is significantly simpler and more transparent, then what was available before. Furthermore, our embedding can be com puted in deterministic linear time in n, given oracle access to the norm.