Return to Answer

Answering Frobenius norm part of the question:

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

$$E[\|X'X\|_F^2]=b(b+1)\operatorname{Tr}\Sigma^2+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

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

There's a remarkably simple formula that explains this behavior. If $x,y,x_i$ are drawn IID from a Gaussian distribution in $\mathbb{R}^d$, we have the following:

$$\mathbb{E}\left\|\sum_i^b x_i x_i^T\right\|_F^2=b\ \mathbb{E}(\|x\|^4)+b(b-1) \mathbb{E}\langle x, y\rangle$$

This means that the value of $\frac{1}{b^2}\|XX^T\|_F^2$ is a weighted mean between $E[\|x\|^4]$ and $\mathbb{E}\langle x, y\rangle$.

Sometimes we can exchange the order of $E$ and reciprocal, which would make quantity in question a weighted harmonic mean between $1/E[\|x\|^4]$ and $1/\mathbb{E}\langle x, y\rangle$, which is the empirical behavior observed in plots above.

Proof:

Matrix multiplication is commutative w.r.t to any Schatten norm, hence we can write $$\left\|\sum_i^b x_i x_i^T\right\|=\left\|X^TX\right\|^2_F=\left\|XX^T\right\|^2_F=\sum_i \sum_j \langle x_i, x_j\rangle^2$$

Here $X$ is formed by stacking $x_i$ as rows, as per-convention for the data matrix in statistics.

Taking the expectation of latter expression we have $b^2$ terms. Because $x_i$ are sampled IID, there are only two kinds of terms: $b$ diagonal terms and $b(b-1)$ off-diagonal terms, result follows.

Alternative ways of writing this result using result for dot produt

$$\mathbb{E}\left\|\sum_i^b x_i x_i^T\right\|_F^2=b\ \mathbb{E}(\|x\|^4)+\frac{1}{2}b(b-1)\left(\mathbb{E}\left[\|x\|^4\right]-\mathbb{E}\left[\|x\|^2\right]^2+2\ \|\mathbb{E}x\|^4\right) $$

Or it can be written in terms of covariance matrix/mean using Gaussian moment result here

Answering Frobenius norm part of the question:

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

$$E[\|X'X\|_F^2]=b(b+1)\operatorname{Tr}\Sigma^2+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

There's a remarkably simple formula that explains this behavior. If $x,y,x_i$ are drawn IID from a Gaussian distribution in $\mathbb{R}^d$, we have the following:

$$\mathbb{E}\left\|\sum_i^b x_i x_i^T\right\|_F^2=b\ \mathbb{E}(\|x\|^4)+b(b-1) \mathbb{E}\langle x, y\rangle$$

This means that the value of $\frac{1}{b^2}\|XX^T\|_F^2$ is a weighted mean between $E[\|x\|^4]$ and $\mathbb{E}\langle x, y\rangle$.

Sometimes we can exchange the order of $E$ and reciprocal, which would make quantity in question a weighted harmonic mean between $1/E[\|x\|^4]$ and $1/\mathbb{E}\langle x, y\rangle$, which is the empirical behavior observed in plots above.

Proof:

Matrix multiplication is commutative w.r.t to any Schatten norm, hence we can write $$\left\|\sum_i^b x_i x_i^T\right\|=\left\|X^TX\right\|^2_F=\left\|XX^T\right\|^2_F=\sum_i \sum_j \langle x_i, x_j\rangle^2$$

Taking the expectation of latter expression we have $b^2$ terms. Because $x_i$ are sampled IID, there are only two kinds of terms: $b$ diagonal terms and $b(b-1)$ off-diagonal terms, result follows.

Alternative ways of writing this result using result for dot produt

$$\mathbb{E}\left\|\sum_i^b x_i x_i^T\right\|_F^2=b\ \mathbb{E}(\|x\|^4)+\frac{1}{2}b(b-1)\left(\mathbb{E}\left[\|x\|^4\right]-\mathbb{E}\left[\|x\|^2\right]^2+2\ \|\mathbb{E}x\|^4\right) $$

Or it can be written in terms of covariance matrix/mean using Gaussian moment result here

There's a remarkably simple formula that explains this behavior. If $x,y,x_i$ are drawn IID from a Gaussian distribution in $\mathbb{R}^d$, we have the following:

$$\mathbb{E}\left\|\sum_i^b x_i x_i^T\right\|_F^2=b\ \mathbb{E}(\|x\|^4)+b(b-1) \mathbb{E}\langle x, y\rangle$$

This means that the value of $\frac{1}{b^2}\|XX^T\|_F^2$ is a weighted mean between $E[\|x\|^4]$ and $\mathbb{E}\langle x, y\rangle$.

Sometimes we can exchange the order of $E$ and reciprocal, which would make quantity in question a weighted harmonic mean between $1/E[\|x\|^4]$ and $1/\mathbb{E}\langle x, y\rangle$, which is the empirical behavior observed in plots above.

Proof:

Matrix multiplication is commutative w.r.t to any Schatten norm, hence we can write $$\left\|\sum_i^b x_i x_i^T\right\|=\left\|X^TX\right\|^2_F=\left\|XX^T\right\|^2_F=\sum_i \sum_j \langle x_i, x_j\rangle^2$$

Here $X$ is formed by stacking $x_i$ as rows, as per-convention for the data matrix in statistics.

Taking the expectation of latter expression we have $b^2$ terms. Because $x_i$ are sampled IID, there are only two kinds of terms: $b$ diagonal terms and $b(b-1)$ off-diagonal terms, result follows.

Alternative ways of writing this result using result for dot produt

$$\mathbb{E}\left\|\sum_i^b x_i x_i^T\right\|_F^2=b\ \mathbb{E}(\|x\|^4)+\frac{1}{2}b(b-1)\left(\mathbb{E}\left[\|x\|^4\right]-\mathbb{E}\left[\|x\|^2\right]^2+2\ \|\mathbb{E}x\|^4\right) $$

Or it can be written in terms of covariance matrix/mean using Gaussian moment result here