The Johnson-Lindenstrauss (JL) Lemma is a important result in mathematics that provides a way to reduce the dimensionality of data points while preserving the pairwise distances between them, up to a certain distortion. In this blog post, we introduce the JL Lemma and present a proof of the theorem.

The proof is based on the work of Dasgupta et al.’s paper An elementary proof of a theorem of Johnson and Lindenstrauss.. For a more detailed explanation, please refer to the original paper.

In the previous post, we introduced the concepts of metric space and embedding, and we discussed two isometric embeddings into the Chebyshev \((\ell_\infty)\) space. However, in many practical scenarios, distortion embeddings are more effective, as they trade precision for computational efficiency.

In this post, we introduce a new embedding that maps points from any metric space into \(\ell_\infty\)-space with appropriate dimensions. Furthermore, we demonstrate that the contraction of this embedding does not exceed a given parameter \(D\).

This embedding was proposed by Matousek in his paper On the Distortion Required For Embedding Finite Metric Spaces into Normed Spaces. For a deeper understanding, we encourage you to refer to the original paper.

An embedding is a mapping that preserves the structure of metric space when transformed into another. By leveraging embeddings, we can reduce complex problem to spaces where more efficient solutions are possible. In this post, we firstl introduce the concepts of metric space and embedding. Then, we demonstract two isometric embeddings: the first maps a finite \(\ell_1\) space to an \(\ell_\infty\) space, and the second maps any finite metric space to an \(\ell_\infty\) space.