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?
Best Answer
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.