# Are Linear Maps resistant to Noise?

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?

• Just a remark: Since $Mx-M^*x = \eta\,x$, you are interested in $\mathbb{E}(|\eta x|)$ for a random matrix $\eta$ and a given vector $x$. I think you should specify the distribution for $\eta$ more clearly (up to now you describe a procedure to generate $\eta$…). It looks like the entries of $\eta$ (viewed vectorized) come from the uniform distribution on the scaled sphere in $n^2$ dimensions. – Dirk Jan 14 at 15:48
• Oh yes, you are right. I'll edit, thanks! – Alfred Jan 14 at 16:21
• If the vectorized $\eta$ is contrained to lie on the sphere, the entries $\eta_{ij}$ are not iid and not normal. – Robert Israel Jan 14 at 21:12
• Robert Israel comment is right. Alfred needs to decide as both situations make sense - I guess the situation is easier when $\eta$ is iid normal (e.g. with given variance for each entry…). – Dirk Jan 14 at 21:15

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.