Let $G_{m, n}$ denote the Grassmannian manifold, i.e. the set containing all possible subspaces of $R^m$ with dimension $n$. Let $E \in G_{m, n}$. We can associate with $E$ an orthogonal projection matrix $\Phi_E$. That is, an $m$ by $m$ by matrix such that $\Phi_E \beta$ gives the projection of $\beta$ into the given $n$ dimensional subspace E.
The following result is provided in the book High Dimensional Probability. I present a rephrased version of it below.
[High Dimensional Probability, Lemma 5.3.2 (p.111)] Let E be uniformly sampled from the Grassmannian. Let $\beta \in R^m$ be a fixed point. Then:
- $\mathbb{E}[\|\Phi_E \beta\|_2^2] = \frac{n}{m} \|x\|^2_2$
- Given any $\epsilon>0$, with probability of at least $1 - 2 \exp (c\epsilon^2 m)$ we have that:
$$ (1 - \epsilon)\sqrt{\frac{n}{m}} \|\beta\|_2 \le \|\Phi_E \beta\|_2 \le (1 + \epsilon)\sqrt{\frac{n}{m}} \|\beta\|_2$$
I illustrate the result with some experiments. I generate $\Phi_E$ by the following procedure: I sample the entries of a matrix $X\in R^{m \times n}$ independently from a standard Gaussian distribution. And then I use SVD decomposition to obtain the projection matrix into the row space of $X$. High Dimensional Probability explain why this yields the desired distribution (p.108, Section 5.2.6).
The bellow image illustrate how, for $\|\beta\|^2_2 = 1$ the norm of the projection concentrates around $\sqrt{\frac{n}{m}}$. It is constant when $m < n$ and once $m>n$ it decays with the $\sqrt{\frac{n}{m}}$. The error bars give the median and interquartile range of $100$ experiments. The full lines gives the mean predicted by the above lemma.
I was curious whether we could obtain similar results for the $\ell_1$ and I did similar experiments.
When $m> n$ it seems it seems $\|\Phi_E \beta\|_1$ concentrates around $c \sqrt{n} \|\beta\|_2$ with high probability for a given constant $c$. From the experimens, I also estimate that $c\approx 0.8$.
My question is can we obtain a lemma similar to what we have for the $\ell_2$ norm, but for the $\ell_1$ norm?
- Can we prove that $\mathbb{E}[\|\Phi_E \beta\|_1^2] = c^2 n \|\beta\|^2_2$ or something similar?
- Can we also obtain some concentration inequalities for $\|\Phi_E \beta\|_1$?
The experiments seem to suggest it to be the case, but I did not manage to do more progress there...
