JL-Lemma, macroscopic dimension of the space of metric spaces and injective hulls

  • Rostislav Matveev (MPI MiS, Leipzig)
Live Stream


Given some collection C of n>>0 data-points, one often is interested not in the particular representation od C, but rather in some intrinsic relations between points in C. An example of such relations could be a distance function on C. Recording such data would require O(n^2)$ numeric entries. For, let's say, n~10^6 this is unrealistic.
If the distance function on C comes from the restriction of the Euclidean distance under some embedding of C in R^N, and one allows some multiplicative error in the distances, Johnson-Lindenstrauß Lemma allows to reduce the dimension of the representation space to O(n . ln n) (which is manageable for n~10^6).
I would like to investigate, whether there are other classes of finite metric spaces, beside Euclidean-embeddable, where similar reduction is possible. One candidate would be delta-hyperbolic spaces.
I will use Gromov's Macroscopic Dimension notion to formulate the problem and to reduce it to the study of the injective hulls of metric spaces.

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail