Optimal (Euclidean) Metric Compression

10/07/2021

∙

by   Piotr Indyk, et al.

∙

0

∙

share

We study the problem of representing all distances between n points in ℝ^d, with arbitrarily small distortion, using as few bits as possible. We give asymptotically tight bounds for this problem, for Euclidean metrics, for ℓ_1 (a.k.a. Manhattan) metrics, and for general metrics. Our bounds for Euclidean metrics mark the first improvement over compression schemes based on discretizing the classical dimensionality reduction theorem of Johnson and Lindenstrauss (Contemp. Math. 1984). Since it is known that no better dimension reduction is possible, our results establish that Euclidean metric compression is possible beyond dimension reduction.