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?

  • $\begingroup$ 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. $\endgroup$ – Dirk Jan 14 at 15:48
  • $\begingroup$ Oh yes, you are right. I'll edit, thanks! $\endgroup$ – Alfred Jan 14 at 16:21
  • $\begingroup$ If the vectorized $\eta$ is contrained to lie on the sphere, the entries $\eta_{ij}$ are not iid and not normal. $\endgroup$ – Robert Israel Jan 14 at 21:12
  • $\begingroup$ 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…). $\endgroup$ – 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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.