JL-Lemma, macroscopic dimension of the space of metric spaces and injective hulls
- Rostislav Matveev (MPI MiS, Leipzig)
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.