0
$\begingroup$

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.

$\endgroup$

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.