# Expected norms of Wishart matrices

Suppose $$x_i \stackrel{\text{i.i.d}}{\sim} \mathcal{N}(\mu,\Sigma)$$. What can we say about dependence on $$b$$ of Frobenius/spectral norm quantities below?

$$f(b)=\left\|\frac{1}{b}\sum_{i=1}^b x_i x_i^T\right\|_F^2$$

$$g(b)=\left\|\frac{1}{b}\sum_{i=1}^b x_i x_i^T\right\|$$

Empirically, the following gives a near perfect fit for some problems, how can this be explained?

$$E\frac{b}{f(b)} \approx \frac{1}{E f(1)}+ \frac{b-1}{Ef(\infty)}$$

$$E\left(\frac{b}{g(b)}\right)^2 \approx \frac{1}{E g(1)}+ \frac{b-1}{Eg(\infty)}$$

For instance, here's a check of this formula against empirically estimated quantities for 1000-dimensional Gaussian centered at zero and covariance matrix having eigenvalues $$1,\frac{1}{2},\ldots,\frac{1}{1000}$$.

notebook

Any pointers appreciated!

Edit we can write $$f(b)$$ in terms of Wishart random variable $$W_b$$ ($$b$$ degrees of freedom, covariance $$\Sigma$$). The following quantity has a simple dependence on $$b$$ (first graph)

$$E\left[\frac{b}{f(b)}\right]=E\left[\frac{b^3}{\operatorname{Tr}(W_b W_b^T)}\right]$$

Motivation: expected value of dot product squared for a random pair of vectors in a batch of size $$b$$ converges to $$\operatorname{Tr}E[xx']^2$$, behavior above suggests a way to estimate this value for finite $$b$$ which in term informs the largest useful batch size in mini-batch SGD, related question

• you might also explicitly write down the corresponding Wishart matrix $W$, and the corresponding expression for $f$ and $g$ (is $f^2={\rm tr}\,WW^\top$ ?) Sep 4, 2022 at 21:02
• @CarloBeenakker updated post. The question is equivalent to asking why $E\left[\frac{b^3}{\operatorname{Tr}(W_b W_b^T)}\right]$ is well predicted by a simple formula in terms of $b$ Sep 4, 2022 at 22:19
• I interpret your finding as the statement that for $n\gg 1$ and $n\gg b$ the function $\mathbb{E}[b/f(b)]$ depends linearly on $b$; then you find the parameters of this line by fitting to two values of $b$ (you take $b=1$ and $b\rightarrow\infty$, but I guess taking $b=1$ and $b=2$ would fit equally well). There is probably a "law of large numbers" that explains why this expectation value scales linearly with the number of samples $b$. Sep 6, 2022 at 6:26
• $f(b)$ is the average value of dot product across all pairs of vectors in batch of size $b$. This converges to $\operatorname{Tr}(\Sigma^2)$, hence $\frac{b}{f(b)}$ eventually scales linearly with $b$. What's more interesting is understanding why $E[1/f(b)]$ scales harmonically with $b$ before having converged to $1/\operatorname{Tr}(\Sigma^2)$ Sep 6, 2022 at 7:59

Answering Frobenius norm part of the question, $$f(b)$$. Still curious how to do the equivalent for $$g(b)$$

Suppose $$X$$ contains $$b$$ IID instances of random variable $$x$$ stacked as rows. Let $$x$$ be distributed as zero-centered Gaussian with covariance $$\Sigma$$. We can show the following

$$f(b)=\frac{1}{b^2}E[\|X'X\|_F^2]=\frac{(b+1)}{b}\operatorname{Tr}\Sigma^2+\frac{1}{b} (\operatorname{Tr} \Sigma)^2$$

To prove this, first note that:

$$\|X^T X\|_F^2=\operatorname{Tr} X^T X X^T X$$

And that for arbitrary R.V. $$x$$ we have $$E[X'XX'X]=bE[xx'xx']+b(b-1)E[xx']E[xx']$$

For Gaussian $$x$$ centered at zero we can apply Wick's theorem to get:

$$E[xx'xx']=2E[xx']E[xx']+E[xx'] \operatorname{Tr}E[xx']$$

Combining these three equations yields the result above