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.
Best Answer
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)..
For the spectral norm, one can argue similarly: the top singular value also concentrates around its mean, and converges to the edge of the spectrum of the pastur-marchenko law. This is explained in great detail in Bai and Silverstein's book on spectral analysis of random matrices.