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.

  • $\begingroup$ what is definition of $\mathbb{E}(||B||_F)$? $\endgroup$
    – R.N
    Nov 7 '15 at 7:44
  • 2
    $\begingroup$ @RaziehNoori en.m.wikipedia.org/wiki/Matrix_norm#Frobenius_norm $\endgroup$
    – user66307
    Nov 7 '15 at 8:06
  • $\begingroup$ since B is symmetric, its matrix norm is the maximum eigen value... $\endgroup$ Nov 7 '15 at 8:36
  • $\begingroup$ There is now also a MO copy of this question: mathoverflow.net/questions/222994/… @felipa I think the fact that you posted it on MO should be mentioned on your post. See this recommendation on meta. $\endgroup$ Nov 9 '15 at 9:09
  • $\begingroup$ Will it be helpful to do it with a normal distribution instead uniform? $\endgroup$
    – Gil
    Nov 9 '15 at 15:24

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;


ans =



ans =


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)$

  • $\begingroup$ 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$. $\endgroup$
    – felipa
    Nov 10 '15 at 13:56
  • $\begingroup$ You are right. What I wrote was on the Frobenius norm of $A$... $\endgroup$
    – Gil
    Nov 10 '15 at 16:09
  • $\begingroup$ How have you gone from knowing $||A||_2$ to giving $||B||_2$? $\endgroup$
    – felipa
    Nov 11 '15 at 10:01
  • $\begingroup$ If $B=A^TA$ then $\Vert B \Vert_2=\Vert A \Vert_2^2$ $\endgroup$
    – Gil
    Nov 12 '15 at 11:48
  • $\begingroup$ 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. $\endgroup$
    – Gil
    Nov 12 '15 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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