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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.