Deviation of Random Projections

91 Views Asked by At

Let $P$ be an orthogonal projection in $\mathbb{R}^n$ onto an $m-$dimensional random subspace uniformly distributed in the Grassmannian $G_{n,m}$. Let $T$ be a bounded subset of $\mathbb{R}^n$. Let $x$ and $y$ be fixed points in $\mathbb{R}^n$ and suppose $\|x\|_2=\|y\|_2=1$. I would like to prove $$ \| \|Px\|_2 - \|Py\|_2\|_{\psi_2} \leq \frac{C}{\sqrt{n}}\|x-y\|_2 $$ where $C$ is an absolute constant and $\|X\|_{\psi_2}$ denotes the subgaussian norm of $X$.

It is easy to prove $\leq C\sqrt{\frac{m}{n}}\|x-y\|_2$. But, I'm trying to find a way to remove $\sqrt{m}$ from the upper bound. Any help is very much appreciated!

This is, I believe, the key component to prove the following deviation inequality, which is given as Exercise 9.1.11 in Roman Vershynin's High-Dimensional Probability. Note that the statement in his book has a typo and I confirmed with the author that the correct statement should be as follows:

$$ \mathbb{E} \sup_{x \in T} \left| \|Px\|_2 - \sqrt{\frac{m}{n}} \|x\|_2 \right| \leq C \frac{\gamma(T)}{\sqrt{n}} $$ where $C$ is an absolute constant and $\gamma (T)$ is the gaussian complexity of $T$.