A Generalization of the Johnson-Lindenstrauss Lemma

Computational methods for real-world data sets often suffer from the "curse of dimensionality"; a common approach is to reduce the dimension of the data while preserving its important structure. The Johnson-Lindenstrauss lemma is a celebrated result in this context: it states that a random (scaled) projection into a lower-dimensional space (approximately) preserves the pairwise distances of a point set with constant probability.

We extend this result by showing that random projections preserve more structure: for any set of k points, the radius of their minimum enclosing ball is preserved with constant probability. We show applications of this result for k-center clustering and for the construction of approximate Cech complexes.