Let $A$ be a random $m$ by $n$ rectangular sign matrix, chosen uniformly at random, with $m < n$. To be clear, $A$ is a matrix whose entries are chosen from $\{1,-1\}$.

Let $B = A^T A$. We know, for example, that $B$ is a square and symmetric $n$ by $n$ matrix with all its diagonal entries equal to $m$ exactly. I am trying to learn how to calculate the expected Frobenius and spectral norm of $B$. We can assume both $m$ and $n$ are large if that helps give a good bound or estimate.

How can you calculate $\mathbb{E}(||B||_F)$ and $\mathbb{E}(||B||_2)$?

The expected Frobenius norm of $B$ is defined to be

$$ \mathbb{E}(||B||_F)=\mathbb{E}\left(\sqrt{\sum_{i=1}^n\sum_{j=1}^n |b_{ij}|^2}\right) $$

where $b_{ij}$ are the elements of $B$.

The expected spectral norm of $B$ is defined to be

$$ \mathbb{E}(||B||_2)= \mathbb{E}\left(\max_{|x|_2 \ne 0}\frac{|Bx|_2}{|x|_2}\right). $$


Cross-posted to https://mathoverflow.net/questions/222994/how-to-calculate-expected-value-of-matrix-norms-of-ata now. I will update this question if anything substantive is added there.

up vote 6 down vote accepted
+50

Here is a try. The matrix entries are Bernoulli random variables, that get a value of $\pm 1$. A Bernoulli random variable is zero mean subgaussian variable with finite moments.

If we define $\lambda = m/n$, then for large values of $m,n$:

$\Vert A \Vert_2 \rightarrow \sqrt{n}\left(1+\sqrt\lambda \right)$

and therefore, $\Vert B \Vert_2 \rightarrow n\left(1+\sqrt\lambda \right)^2$

Asymptotically, $\Vert A \Vert_2 = \sqrt m+\sqrt n$ and $\Vert B \Vert_2=(\sqrt m + \sqrt n)^2$.

Here is the reference I used: http://www-personal.umich.edu/~romanv/papers/rv-rectangular-matrices.pdf

Another good reference is "Smallest singular value of random matrices and geometry of random polytopes" by Litvak et. al.

I tried it in MATLAB and it seems to be working well:

A = sign(rand(1e5,10)-0.5); c = 10/1e5;

sqrt(1e5)*(1+sqrt(c))

ans =

319.3900

norm(A)

ans =

318.8748

Now, for the Frobenius norm. The goal is to compute for start $\mathbb{E}(\Vert B \Vert_F^2)$. Let's divide it for two cases:

1) The diagonal part: very simple, since the elements are always $m$ the total contribution of the diagonal is $nm^2$.

2) The off-diagonal part ($i \neq j$): note that $\mathbb{E}(b_{ij})=0$ for $i\neq j$, so using the facts the RVs are iid, we get: $\mathbb{E}(b_{ij}^2)=\mathrm{Var}(\sum_k a_{ik}a_{jk})=\sum_k \mathrm{Var}(a_{ik}a_{jk})=m$, (again, for $i \neq j$). All in all, $n(n-1)$ off-diagonal elements.

Summing it all gives: $\mathbb{E}(\Vert B\Vert_F^2)=nm^2+n(n-1)m=nm^2+n^2m-mn$.

Using Bernstein's inequality for Bernoulli random variables with probability $\frac{1}{2}$, for large matrix the variance decays exponentially, and therefore $\sqrt{\mathbb{E}(\Vert B\Vert_F^2)} \rightarrow \mathbb{E}(\Vert B\Vert_F)$

  • I think the Frobenius norm answer is wrong unfortunately. Take the matrix with one row $A=(1,1,1,1)$. $A^TA$ is a $4$ by $4$ all ones matrix with Frobenius norm 4. But your answer suggests it should be $\sqrt{1*4} = 2$. – felipa Nov 10 '15 at 13:56
  • You are right. What I wrote was on the Frobenius norm of $A$... – Gil Nov 10 '15 at 16:09
  • How have you gone from knowing $||A||_2$ to giving $||B||_2$? – felipa Nov 11 '15 at 10:01
  • If $B=A^TA$ then $\Vert B \Vert_2=\Vert A \Vert_2^2$ – Gil Nov 12 '15 at 11:48
  • btw, I thought of it and computing $\mathbb{E}(\Vert B \Vert_F^2)$ should not be difficult. The question is if it is helpful or only $\mathbb{E}(\Vert B \Vert_F)$ is interesting to you. – Gil Nov 12 '15 at 14:03

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.