Johnson Lindenstrauss Lemma proof

267 Views Asked by At

Just trying to understand the text below.

Question 1: What exactly is the argument below (1)? "This is enough because applying (1) to $v=x-y$ for $x,y\in\mathbb{R}^n$, we get $f(x,y)=f(x)-f(y)$, and by a union bound over $\pmatrix{n\cr2}$ pairs $x\ne y\in X$ the theorem follows" where are $x,y$ come from? How the union bound is applied? If $X$ is a subspace of $l^2$, then there should be many more points than $\pmatrix{n\cr2}$.

Question 2: How is 3 chosen in the second to last line? Is this important?

enter image description here enter image description here

Here is the main theorem this is trying to prove.

enter image description here

And here's the link to the text http://www.wisdom.weizmann.ac.il/~robi/teaching/2009b-SeminarGeometryAlgs/scribe5.pdf