Johnson Lindenstrauss Lemma
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.
JL Lemma
For any set
where
Let
Proof of JL Lemma
To prove the JL Lemma, we first establish some auxiliary lemmas and inequalities. For convenience, we will omit the subscript
Lemma 1
For any point
Proof of Lemma 1
From the definition of
Now, we compute
- if
, then: - if
, then:
Thus, we get:
Lemma 2
Let
Proof of Lemma 2
The PDF of the standard normal distribution is:
We now compute
Next, let
Using the well-known result for the standard normal distribution:
Therefore:
Lemma 3
For any point
Proof of Lemma 3
We begin by simplifying the inequalities. From the definition of
We now compute
Since the standard normal distribution is a
where
For the first inequality, let
Using the Markov’s inequality, we have:
Let
Using the Taylor expansion for
We have:
Thus:
If
then:
Therefore:
Similarly, for the second inequality, let
Let
Similarly, using the Taylor expansion for
we have:
Thus:
Therefore:
Proof of the JL Lemma
Given any point
From Lemma 3, for any point
Since this probability holds for any point
Furthermore, using the linearity of the projection, we have:
Therefore, applying Lemma 3 to the difference between two points
The number of pairs of points
Thus, with probability at least