Is Johnson-Lindenstrauss Lemma related to concentration of measure around the equator?

44 Views Asked by At

The Johnson-Lindenstrauss Lemma is a very strong result related to dimension resuction. Most proves uses the concentrasion of Gaussian variables. I'm trying to understand its geometric essense.

If we state Johnson-Lindenstrauss on a unit ball, one version is like this (See Corollary 3.4 in this article):

Let $\mu$ be the only rotation-invariant Radon probability measure on the $(D-1)$ dimensional unit ball $\mathbb S^{D-1}$ and let $L \subseteq \mathbb R^D$ be a $d$-dimensional subspace of $\mathbb R^D$. Let $\Pi_{L}$ be the projection onto $L$ (i.e. $\Pi_L(x) = \arg\min_{z \in L} \|z - x\|$), then we have for any $\epsilon \in (0,1)$, \begin{align} \mu \left\{x \in \mathbb S^{D-1} \left| (1-\epsilon)\|x\| \leq \sqrt{\frac{D}{d}} \|\Pi_L(x)\| \leq (1 - \epsilon)^{-1}\|x\| \right.\right\} \geq 1 - 2 \exp\left(-\frac{\epsilon^2 d}{4}\right). \end{align}

This implies that on a unit ball, consider an arbitrary $d$-dimensional subspace $L$, then most points will be in the area whose distance to $L$ is closed to $\frac{D-d}{D}$ (notice that $\|x\| = 1$).

There is also another result, which is usually referred to as concentrasion of measure, saying that most points on a unit ball are concentrated around the equator.

The equator on a $(D-1)$ dimensional ball can be viewed as the intersection of the ball with a $(D-1)$ dimensional subspace. The concentration around the equator can be also stated as: Most points on a $(D-1)$ dimensioanl unit ball are concentrated around an arbitrary $(D-1)$ dimensional subspace. To me this looks very simialr to the JL lemma (It's kind of like a $d = D-1$ spacial case).

I think the commen proof of JL lemma based on the concentration of Gaussian variables somewhat lack geometric intuition and is harder to generalize. My question is, is it possible to prove JL lemma using the concentration around the equator? (or a proof in a similar spirit). I think the latter gives a better geometric intuition.