# Restricted Isometry Property for Random Orthogonal Projections

The following is from Roman Vershynin's: High-Dimensional Probability: An Introduction with Applications in Data Science.

Let $$P$$ be the orthogonal projection in $$\mathbb{R}^n$$ onto an $$m-$$dimensional subspace uniformly distributed in the Grassmannian $$G_{n,m}$$.

Prove that $$P$$ satisfies the Restricted Isometry Property with parameters similar to $$\alpha=0.9 \sqrt{m}$$, $$\beta=1.1 \sqrt{m}$$ and sparsity $$s$$, up to a normalization.

The parameters above are in reference to a previous theorem in the text proving the RIP for $$m \times n$$ matrices with sub-Gaussian, isotropic, independent rows.

The Restricted Isometry Property reads as follows:

An $$m \times n$$ matrix $$A$$ satisfies the Restricted Isometry Property (RIP) with parameters $$\alpha$$, $$\beta$$ and $$s$$ if the inequality: $$\begin{equation} \alpha ||\textbf{v}||_2 \leq ||A \textbf{v} ||_2 \leq \beta ||\textbf{v}||_2 \end{equation}$$ holds for all $$s-$$sparse $$\textbf{v} \in \mathbb{R}^n$$.

What I have so far:

It can be verified that if $$A$$ is an $$n \times m$$ matrix whose entries $$A_{i,j}$$ ~ $$\mathcal{N}(0,1)$$ are independent unit Gaussians, then $$RA$$ and $$A$$ have the same distribution, where $$R \in SO(m)$$, under the right normalization (I believe it should be $$\sqrt{\det (A A^T) }$$ ), $$\frac{A}{\sqrt{\det (A A^T) }}$$ will be uniformly distributed on the Grassmannian, and is in fact the Haar measure on the Grassmannian, by uniqueness of Haar measure.

I am still fuzzy on the details as to why this normalization "puts $$A$$ on the Grassmanian", it seems analagous to normalizing a Gaussian vector to put it on the sphere and thus produce a uniform distribution on the sphere. The case of the sphere is more or less straight forward because we can embed the sphere $$\mathbb{S}^{n-1}$$ into $$\mathbb{R}^n$$, so we can work concretely in coordinates. I think in the case of the Grassmannian, some identification must be made with $$SO(n)/(SO(m) \times SO(n-m))$$ but I am not so adept at working with these spaces.

I am also unsure how to relate this to the orthogonal projection in a tractable way. There is an exact correspondence between orthogonal projections and the subspaces they project onto, and in fact you can construct the projection from the subspace ($$P=A^T(AA^T)^{-1} A$$) but this seems like it would be difficult to analyze the RIP for such a matrix. I think there must be some way to analyze $$A$$ directly to get the result, but I am stuck on how to make the connection.