Johnson-Lindenstrauss with Orthogonalization

Question

I have been looking at constructions satisfying the Johnson-Lindenstrauss Lemma (e.g., projections onto random subspaces, random Gaussian matrices, random Rademacher matrices, etc.). It seems that other than the "random subspace" construction, none of the other projections are true projections in the sense that the vectors are not orthonormalized. Is this purely out of convenience/efficiency?

More formally, suppose a matrix $X$ with $X_{ij} \sim \text{Rademacher}(1/2)$ preserves distances with high probability. Is it also true that $P_X := X^\top(XX^\top)^{-1}X$ will also preserve distances with the same probability?

The most general version of the JL lemma that I have been able to find is here, which shows that any matrix with mean-zero, unit-variance, uniformly subgaussian, and independent entries satisfies the Lemma, but that clearly does not hold for $P_X$.

Answer 1

Suppose $v$ has unit norm and $\|Xv\|\in[1-\epsilon,1+\epsilon]$. Then $$\|X^\top(XX^\top)^{-1}Xv\|=\|(XX^\top)^{-1/2}Xv\|\in\bigg[\frac{1-\epsilon}{\sigma_\max(X)},\frac{1+\epsilon}{\sigma_\min(X)}\bigg].$$ If $X$ has subgaussian entries, then one may control its extreme singular values with standard techniques. (See Vershynin's treatment, for example.) Then a union bound gives that the random projection $X^\top(XX^\top)^{-1}X$ is JL with slight loss in the distortion parameter $\epsilon$.