8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Yemon Choi Nov 9 '15 at 18:31
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – felipa Nov 12 '15 at 20:08

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.