Are Linear Maps resistant to Noise?

Question

Let's assume I have a $m \times m$ matrix $M$ with Frobenius norm $1$ and a unit vector $x \in S^{m-1}$. I also have a second $m \times m$ matrix $M^*$ which is obtained from the first one plus some injected noise $\eta$, where every entry $\eta_{i,j}$ is i.i.d. and comes from a normal distribution with mean $0$ and variance such that $||\eta||_F = 1/10$. In other words, as Dirk pointed out in the answer,the entries of η (viewed vectorized) come from the uniform distribution on the scaled sphere in $n^2$ dimensions.

What can we say about the following expected value $$\mathbb{E}[| Mx - M^*x|]?$$

I know that $\mathbb{E}|\eta(x)| <1/10$ since, because of the frobenius norm of the noise $|\eta(x)| < 1/10$, so the equality only holds when vector $x$ is aligned with the highest eigenvector of the noise matrix $\eta$, but this happens with low probability, and this probability should (intuitively) change with respect to $m$: in a higher dimensional space the probability of two random vectors having a similar direction is lower than in a 2-dimensional one.

Is there a way to improve the bound on this expected value?

Answer 1

I'm assuming the vectorized $\eta$ is uniformly distributed on the sphere of radius $1/10$ in $\mathbb R^{n^2}$.

For fixed $x$, $$ \mathbb E \| \eta x \|_2^2 = \mathbb E \sum_i \sum_j \sum_k \eta_{ij} \eta_{ik} x_j x_k = \sum_j \sum_k \mathbb E (\eta^T \eta)_{jk} x_j x_k $$

Now for $j = k$, $$ \mathbb E(\eta^T \eta)_{kk} = \sum_i \mathbb E \eta_{ik}^2 = \frac{1}{n} \sum_{i}\sum_j \eta_{ik}^2 = \frac{1}{100 n}$$ while for $j \ne k$, since the conditional distribution of $\eta_{ij}$ given $\eta_{ik}$ is symmetric about $0$, $$\mathbb E(\eta^T \eta)_{jk} = \sum_i \mathbb E(\eta_{ij} \eta_{ik}) = 0$$ Thus $$ \mathbb E \|\eta x\|_2^2 = \sum_k \frac{1}{100 n}x_k^2 = \frac{\|x\|_2^2}{100n}$$

I suspect more can be said about the distribution of $\|\eta x \|$ using concentration of measures, but I'll leave that to someone else.