1
$\begingroup$

1 - Let A be a matrix whose entries are I.i.d of Normal(0,1).

Is there any information, or distribution about the spectral norm of A?

...

2 - Main question: now B is a matrix whose columns are independent unit norm vectors, drawn from $\mathbb{S}^{n-1}$ uniformly.

What can we say about the average spectral norm of B? or distribution?

...

I asked the first question because normalizing each column of A is B so......

I thought it might be related......

$\endgroup$

1 Answer 1

1
$\begingroup$

Much is known about $A$; here are some relevant keywords. This distribution on random matrices is called the Ginibre ensemble (although that term sometimes refers to the square case only). The corresponding distribution on the covariance matrix $A^T A$ is the Wishart distribution. The joint density of its eigenvalues can be written down explicitly (it's in the Wikipedia article). If $A$ is an $n \times m$ matrix and $m, n \to \infty$ at comparable rates the spectral norm is asymptotic to $\sqrt{m} + \sqrt{n}$, and the fluctuations around this norm satisfy the Tracy-Widom law. See, for example, Theorem 2.5 and Theorem 2.6 in Djalil Chafai's Singular values of random matrices.

$B$ ought to behave roughly like $\frac{A}{\sqrt{n}}$ so I think this means the spectral norm ought to be asymptotic to $1 + \sqrt{ \frac{m}{n} }$ but I'm not savvy enough to deduce these results from known results; random matrices often exhibit "universality" so different distributions can often behave similarly but I don't know a reference where this particular random matrix distribution is studied or what it's called. If you only want the average norm it may be possible to do calculations by hand by taking traces of powers.

Edit: Okay, so let's try to analyze $B$ by hand. Let $v_1, \dots v_m \in S^{n-1}$ be the columns of $B$, so that $W = B^T B$ is the $m \times m$ Gram matrix $W_{ij} = \langle v_i, v_j \rangle$. The eigenvalues of $W$ are the squares $\sigma_i(B)^2$ of the singular values of $B$, and $\sigma_1(B) = \| B \|$ is the spectral norm, so

$$\text{tr}(W^k) = \sum_{i=1}^n \sigma_i(B)^{2k}$$

which gives (deterministic) upper and lower bounds

$$\sqrt[k]{ \frac{\text{tr}(W^k)}{\text{min}(n, m)} } \le \| B \|^2 \le \sqrt[k]{\text{tr}(W^k)}.$$

The first easy calculation is that $\text{tr}(W) = \sum_{i=1}^m \| v_i \|^2 = m$ which gives $\sum_{i=1}^m \sigma_i(B)^2 = m$ and hence

$$\sqrt{ \frac{m}{\text{min}(m, n)} } \le \| B \| \le \sqrt{m}.$$

Next we have

$$\text{tr}(W^2) = \sum_{i, j} \langle v_i, v_j \rangle \langle v_j, v_i \rangle = \sum_{i, j} \langle v_i, v_j \rangle^2$$

so

$$\mathbb{E}(\text{tr}(W^2)) = m + m(m-1) \text{Var}(\langle v_1, v_2 \rangle).$$

The distribution of a dot product $\langle v_1, v_2 \rangle$ of two random unit vectors is known and in particular the variance is known to be $\frac{1}{n}$, which gives

$$\mathbb{E}(\text{tr}(W^2)) = \sum_{i=1}^n \mathbb{E}(\sigma_i(B)^4) = m + \frac{m(m-1)}{n}$$

and hence

$$\frac{m + \frac{m(m-1)}{n}}{\text{max}(m, n)} \le \mathbb{E}(\| B \|^4) \le m + \frac{m(m-1)}{n}.$$

In general the combinatorics involved in understanding $\mathbb{E}(\text{tr}(W^k))$ seem very complicated; unlike the analysis of matrices with iid entries (for which see, for example, this blog post by Terence Tao) we have less independence to play with. So to do this analysis by hand maybe another approach is needed. We could try working with

$$\| B \| = \sup_{\| v \| = 1} \| Bv \|$$

instead.

$\endgroup$
2
  • $\begingroup$ Thank you for your kind answer. Both of your answers are very helpful for me. Have you ever heard of $1+\sqrt{\log \log n}$ bound for problem 2? It seems like the spectral norm follows such a tendency. $\endgroup$ Oct 15, 2020 at 1:36
  • $\begingroup$ @user2998690: I'm not willing to say anything confident about the distribution of $B$! $\endgroup$ Oct 15, 2020 at 2:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .