Adaptive Robustness of Hypergrid Johnson-Lindenstrauss

Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for n > m, a scaled random projection A from ℝn to ℝm is an approximate isometry on any set S of size at most exponential in m. If S is larger, however, its points can contract arbitrarily under A. In particular, the hypergrid ([−B, B] ∩ ℤ)n is expected to contain a point that is contracted by a factor of κstat = Θ(B)−1/α, where α = m/n.