# How to calculate expected value of matrix norms of $A^TA$?

Let $A$ be a random $m$ by $n$ rectangular sign matrix, chosen uniformly at random, with $m < n$. 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 work out how to calculate (or estimate) the expected Frobenius and spectral norm of $B$. We can assume both $m$ and $n$ are large.

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

I apologize if this turns out to be simple to do. I previously asked at https://math.stackexchange.com/questions/1517103/how-to-calculate-expected-value-of-matrix-norms-of-ata with no answer.

• One minor comment: usually it is easier to work with the square of the Frobenius norm, and then one can appeal to concentration inequalities that tell us the variance of the Frobenius norm of a random matrix is (usually) much smaller than its expected value as the matrix size tends to infinity – Yemon Choi Nov 9 '15 at 18:31

Expanding a bit on Yemon Choi's comment: concentration is indeed the key. First, $\|B\|_F^2$ is simply the sum of the squares of singular values of $A$, and $E\|B\|_F^2=m(m-1)n+mn^2$. On the other hand by standard concentration inequalities (using that $\|B\|_F^2=\sum \sigma_i^4$ where $\sigma_i$ are the singular values of $A$), you obtain an exponential (in fractional power of m) concentration around the mean, which is good enough to also conclude that $E\|B\|_F/\sqrt{m^2n+mn^2}\to 1$ (as both $m$ and $n$ grow)..
• Thank you for this. In an answer to the linked math.se question it is claimed that $\mathbb{E}(\Vert B \Vert_2)$ is asymptotic to $(\sqrt m + \sqrt n)^2$. – felipa Nov 12 '15 at 20:08