I have some questions about proof of Johnson-Lindenstrauss (JL) lemma. I appreciate any responses in advance.
It is stated in the following paper: An elementary proof of JL lemma we argued: "Hence the aim is to estimate the length of a unit vector in $\mathbb{R}^{d}$ when it is projected onto a random k-dimensional subspace. However, this length has the same distribution as the length of a random unit vector projected down onto a fixed k-dimensional subspace." I have no clue why this is the case.
In the JL context by projection of a vector we mean $u=\mathbf{A}v$ where $\mathbf{A} \in \mathbb{R}^{k \times d}$, $v \in \mathbb{R}^{d}$ and $u \in \mathbb{R}^{k}$, right? If the answer is yes, how about the case that instead of $\mathbf{A}$ we have access to the projection operator (matrix) $\mathbf{P} \in \mathbb{R}^{d \times d}$ to the k-dimensional subspace. What can we say about distribution of $||\mathbf{P}v||_{2}$, that is, distribution of norm after projection? Is the result equivalent to the previous (common) case? If yes, why?
Again, any comment, answer, or reply is appreciated.
For the first question, I received the following answer from a friend:
"This is how I understand it. This is not rigorous, but it gives the intuition. Consider the case of projecting a unit vector $u$ in $\mathbb{R}^{d}$ onto a random $k$-dimensional subspace. One way of selecting a random $k$−dimensional subspace is through randomly selecting $k$ orthonormal vectors that form the basis of the subspace. Lets assume we randomly selected these $k$ vectors. Now lets rotate the coordinate axis such that our $k$ vectors become the first $k$ standard basis. This operation doesn't change the length of projection of $u$ onto the subspace. Now consider the point $u$ in this rotated space. Since we randomly selected our $k$ vectors (independent of $u$), we expect $u$ to be uniformly distributed in the rotated space. So intuitively, the length of $u$ projected onto a random subspace has the same distribution as the length of a random unit vector projected onto a fixed $k$-dimensional subspace."
For the second question, I was able to verify by means of simulation that expected value of $||A^{T}u||_2$ is approximately equal to expected value of $||Pu||_2$ where $A$ is a basis (not necessarily orthogonal) for the $k$-dimensional subspace and $P=AA^{\dagger}$ is the orthogonal projection operator onto the $k$-dimensional subspace. However I cannot provide a proof for this argument yet.