I'm trying to find an upper bound for the following expression
$$ \mathbb{E} || \Psi_2^{+} \Psi_1 A ||_F $$ Where $A \in \mathbb{R}^{(n-k) \times m}$ is fixed, and the matrices $\Psi_1 \in \mathbb{R}^{\ell \times (n-k)} ,\Psi_2 \in \mathbb{R}^{\ell \times k} $ are random matrices, generated by the following process: $$ \Psi_1 = \Psi V_1 \text{ and } \Psi_2 = \Psi V_2 $$ where $V = [V_1 , V_2] \in \mathbb{R}^{n \times n}$ is unitary (hence $V_1 \in \mathbb{R}^{n \times (n-k)}$ and $V_2 \in \mathbb{R}^{n \times k}$ have orthonormal columns, and $V_2^T V_1 = 0$). The matrix $\Psi \in \mathbb{R}^{\ell \times n}$ is a random matrix whose entries are uncorrelated and such that mean and variance of the entries are, respectively, zero and $\sigma^2$. We assume that $\ell > k + 1$
The goal is to obtain an (over)estimate in the form of $$ \mathbb{E} || \Psi_2^{+} \Psi_1 A ||_F \leq G ||A ||_F := G(\Psi_2 , \Psi_1 , n , \ell, k) || A ||_F $$
That is, the coefficient $G$ should be an expression containing $\Psi_2 , \Psi_1$ and their sizes.
For example, if $\Psi$ was a standard normal matrix, then so was $\Psi V = [\Psi_1 , \Psi_2]$ and as a result, we would have that $\Psi_1$ and $\Psi_2$ are both standard normal matrices and are independent. In this case, $$ \begin{align} \mathbb{E} || \Psi_2^{+} \Psi_1 A ||^2_F &= \mathbb{E}_{\Psi_2} \left( \mathbb{E}_{\Psi_1} || \Psi_2^{+} \Psi_1 A ||^2_F \right) \\ &= \mathbb{E}_{\Psi_2} ||\Psi_2^{+}||_F^2 ||A||_F^2 \\ &= \frac{k}{n - k -1} ||A||_F^2 \end{align} $$
where the first relation is due to the independence between $\Psi_1 ,\Psi_2$ which allows for the transition to iterated expectation. The second transition is due to the fact that $\mathbb{E} || BGC ||_F^2 = ||B||_F^2 ||C||_F^2$ for fixed matrices $B,C$ and standard normal $G$. The last equality is due to that $\mathbb{E} || G^+ ||_F^2 = \frac{s}{t-s-1} $ for standard normal matrix $G \in \mathbb{R}^{t \times s}$ with $t>s+1$.
Statements and proofs for the last two facts can be found here.
Alas, in our case, $\Psi$ is not a standard normal matrix. Concretely, the structure of $\Psi$ is given by a Kronecker product of $d$ standard normal matrices: $$ \Psi = S_1 \otimes S_2 \otimes \cdots \otimes S_d $$ where $S_j \in \mathbb{R}^{r_j \times I_j}$ for $j=1,\dots,d$ (it is possible to show that the entries of $\Psi$ are uncorrelated and that they have zero mean and the same variance).
In this case, I have estimations:
- $\mathbb{E}_{\Psi_1} || B \Psi_1 C ||_F^2 = f ||B||_F^2 ||C||_F^2 $ (for fixed $B,C$) and
- $\mathbb{E}_{\Psi_2} ||\Psi_2^{+}||_F^2 = g$.
The problem is, that $\Psi_1,\Psi_2$ are not independent (or at least - I cannot come up with an explanation for why would the be).
What I tried so far, is estimating a bound of an alternative expression: $\mathbb{E} || \Psi_2^{+} \bar{\Psi}_1 A ||^2_F$ for $\bar{\Psi}_1 = \bar{\Psi} V_1$ where $\bar{\Psi}$ generated similarly to, and independently of $\Psi$, so $\bar{\Psi}_1$ and $\Psi_2$ are independent. And it follows that
$$ \begin{align} \mathbb{E} || \Psi_2^{+} \bar{\Psi}_1 A ||^2_F &= \mathbb{E}_{\Psi_2} \left( \mathbb{E}_{\bar{\Psi}_1} || \Psi_2^{+} \bar{\Psi}_1 A ||^2_F \right) \\ &= f \mathbb{E}_{\Psi_2} ||\Psi_2^{+}||_F^2 ||A||_F^2 \\ &= fg ||A||_F^2 \end{align} $$
Surely, this expectation is not the same as the one of the original expression where $\Psi_1,\Psi_2$ may be dependent, and, at least empirically, it seems that $\mathbb{E} || \Psi_2^{+} \bar{\Psi}_1 A ||^2_F \ll \mathbb{E} || \Psi_2^{+} \Psi_1 A ||^2_F$. The next step in this requires to understand the relation between the expected values of the two expressions, i.e., find an $\alpha$ such that $\mathbb{E} || \Psi_2^{+} \Psi_1 A ||^2_F \leq \alpha \mathbb{E} || \Psi_2^{+} \bar{\Psi}_1 A ||^2_F$.
I'm looking for ideas how to do so (if it is even possible), and also open to learn about approaches completely different than my current attempt.