Random projection a fixing vector is equivalent to projecting a random vector

Question

In the book Vershynin the following exercise is presented:

Let $P$ be a projection in $\mathbb{R}^n$ onto a random $m$-dimensional subspace $E \sim \mbox{Unif}(G_{n,m})$, where $G_{n,m}$ is the Grassmanian, the set of $m$-dimensional linear subspaces of $\mathbb{R}^n$. Let $Q$ be a $m \times n$ matrix obtained by choosing the first $m$ rows of a random $n \times n$ matrix $\sim \mbox{Unif}( O(n) )$, namely drawn uniformly from the orthogonal group.

(a) show that for any fixed point $x \in \mathbb{R}^n$, $\| P x \|_2$ and $\|Q x\|_2$ have the same distribution,

(b) show that, for any fixed point $z \in \mathbb{S}^{m-1}$, $$ Q^T z \sim \mbox{Unif} ( \mathbb{S}^{n-1}), $$ where $\mathbb{S}^{n-1} \subset \mathbb{R}^n$ is the $n-1$ dimensional unit sphere and here Unif means uniform distribution in $\mathbb{S}^{n-1}$.

I think that one should use the singular value decomposition for $P$ and make use of the rotational invariance but I am not able to figure our how. Does anyone have a suggestion?

Answer 1

The construction of $Q$ provides a (fairly) concrete realization of a uniformly distributed random Grassmanian and the associated orthogonal projection $P$.

More precisely, let ${\cal L}_n={\rm Unif} (O(n))$ be the law of uniformly distributed orthogonal $n\times n$-matrices. This law is by definition (Fact 1) right and left-invariant under multiplication by any $R\in O(n)$. If $U\sim {\cal L}_n$ then also $RU\sim {\cal L}_n$ and $UR\sim {\cal L}_n$.

Let $\pi=\pi_{m,n} \in M_{m,n}$ be the matrix selecting the $m$ first rows. Then (Fact 2) the law of $Q=\pi_{m,n} U$ is also invariant under right-multiplication by $R_n\in O(n)$. [In fact it is also invariant under left-multiplication by $S_m\in O(m)$ but this is not needed here].

Now, if $z\in {\Bbb R}^m$ is a unit vector, then so is $Q^t z$ (since $Q Q^t=\pi \pi^t={\bf 1}_m$) and by Fact 2 its distribution is the same as that of $R_n^t Q^t z$ for any $R_n\in O(n)$. Thus $Q^t z$ must be uniformly distributed in $S^{n-1}$.

The image $E=Q^t ({\Bbb R}^m)$ is a random $m$-dimensional subspace again uniformly distributed as required and $P=Q^t Q$ provides the realization of the abstract orthogonal projection onto $E$. Then for every $x\in {\Bbb R}^n$: $$ \|Px \|_2 = \|Q^t Q x\|_2 = \|Q x\|_2.$$ So the above norms will follow the same law.

Answer 2

For (a), one approach is to show that the distribution of $\|Px\|_2$ where $P$ is random and $x$ is fixed is the same as the distribution of $\|Px\|_2$ when $P$ is fixed and $x$ is random. All this really uses is rotational invariance (i.e., invariance under orthonormal changes of basis).

Formally, we proceed as follows: Let $S\in O(n)$ be fixed, and let $P$ be drawn randomly from the Grassmanian manifold $G_{n,m}$. Because multiplication by $S$ is an orthonormal change of basis and the Grassmanian does not depend on choice of basis, $P\sim S^\top P S$. Because this is true for any fixed $S$, if we take $T\sim \mathrm{Unif}(O(n))$, then $P\sim T^\top P T$ as well. So $$ \|Px\|_2\sim \|T^\top PT x\|_2 = (PTx)^\top TT^\top (P T x) = \|PTx\|_2. $$ Let $y = Tx$. I claim $\|Py\|_2\sim\|\pi y\|_2$ for any fixed $P\in G_{n,m}$, where $\pi\in G_{n,m}$ is the projection onto the first $m$ coordinates. Since $P$ is a projection, it has singular value decomposition $P = S^\top\pi S$ for $S\in O(n)$. It follows that $\|Py\|_2=\|\pi S y\|_2\sim\|\pi y\|_2$, where we use the fact that $S T \sim T$ because $\mathrm{Unif}(O(n))$ is invariant under orthonormal changes of basis. To finish, observe that we can write $Q = \pi T$, so $Qx\sim \pi Tx = \pi y$.

For (b), we have $Q^\top z\sim (QT)^\top z = T^\top (Q^\top z)$, for $T\sim\mathrm{Unif}(O(n))$, using similar reasoning as above.