On low dimensional local embeddings

摘要

We study the problem of embedding metric spaces into low dimensional lp spaces while faithfully preserving distances from each point to its k nearest neighbors. We show that any metric space can be embedded into [EQUATION] with k-local distortion of O ((log k)/p). We also show that any ultrametric can be embedded into [EQUATION] with k-local distortion 1 + ε.