# Multivariate normal concentration

If $X\sim N(0,\Sigma)$ for some $d$-dimensional normal distribution, then $X = \Sigma^{1/2} Z$ where $Z\sim (0,I)$. How to compute the following quantity? $$\operatorname{var} (X^T X) = \operatorname{var}(Z^T \Sigma Z)$$ Moreover, if we are in the growing dimension regime, under what condition posed on $\Sigma$ (such as restricted strong convexity) do we have as $d\to\infty$ the following? $$\operatorname{var}\left( X^\top X \right) = o(d^2)$$

Update: do we have some sort of concentration inequality for $X^T X$?

Let $$Y := Z^T \Sigma Z$$. We have $$\operatorname{var}(Y) = \mathbb{E}(Y^2) - \mathbb{E}(Y)^2$$ and $$\mathbb{E}(Y) = \sum_i \sigma_{i, i}$$. We thus need to compute $$\mathbb{E}(Y^2)$$. For this, write $$\mathbb{E}(Y^2) = \mathbb{E}\left( \sum_{i, j, k, \ell} Z_i Z_j Z_k Z_\ell \sigma_{i, j} \sigma_{k, \ell} \right) = \sum_{i, j, k, \ell} \mathbb{E}\left(Z_i Z_j Z_k Z_\ell \right) \sigma_{i, j} \sigma_{k, \ell}$$ Due to $$\mathbb{E}\left(Z_i \right) = 0$$, the only non zero contribution of this last expectation comes from the indices such that $$i = j \neq k = \ell$$ (plus the permutations of this case) or $$i = j = k = \ell$$. In the first case, we have $$\mathbb{E}\left(Z_i^2 \right) = 1$$ and in the second case, $$\mathbb{E}\left(Z_i^4 \right) = 3$$.

In the case $$\pi_1 := (i = j \neq k = l )$$ the sum becomes $$(\sum_{i \neq k} \sigma_{i, i} \sigma_{k, k} )^2 = (\sum_i \sigma_{i, i})^2 - \sum_i \sigma_{i, i}^2$$ and in the cases $$\pi_2 := (i = k \neq j = l)$$ and $$\pi_3 := (i = l \neq j = k)$$, it is equal to $$\sum_{i \neq j} \sigma_{i, j}^2 = \sum_{i,j} \sigma_{i, j}^2 - \sum_i \sigma_{i, i}^2$$. Summing, we get $$\mathbb{E}(Y^2) = 2 \sum_{i, j} \sigma_{i, j}^2 + \left( \sum_i \sigma_{i, i} \right)^2 - 3 \sum_i \sigma_{i, i}^2 + 3 \sum_i \sigma_{i, i}^2$$ hence, the variance is $$\operatorname{var}(Y) = 2 \sum_{i, j} \sigma_{i, j}^2$$

Concerning your question on the regime $$d \to \infty$$, you can for instance suppose that $$\max_{i } \sigma_{i, j}^2 = o(1)$$ to get $$\operatorname{var}(Y) = o(d)$$ (with the trivial inequality $$\sum_i \sigma_{i, j}^2 \leq d \max_i \sigma_{i, j}^2$$). You can also put hypotheses directly on the quantity of interest, namely $$\sum_{i, j} \sigma_{i, j}^2$$.

• Thanks! I think I need $var(Y) = O(d) = o(d^2)$, and that should be achieved by your derivation. Aug 15 '17 at 8:49
• If you are satisfied with the answer, maybe you can accept it :) (and also for your other answers, I just had a look). You just need to click on the side. Aug 18 '17 at 0:38
• Ah I just know how to do it. Thanks! Aug 18 '17 at 21:17
• I don't believe this answer is correct. Let $\Sigma = I_d$, then $X^T X \sim \chi^2_d$ and $\operatorname{Var}[X^T X] = \operatorname{Var}[\chi^2_d] = 2d$, but the result given here is $2d^2 + 3d$.
– user114668
Feb 18 '19 at 11:34
• Indeed, I messed up in the partition cases (this is different in bi-dimensional indices compared to the usual vector indexed only in a one-dimensional way). I also wrote $\sigma^2$ in lieu of $\sigma$ (this was a clear mistake since we have a quadratic form and not a bi-quadratic form). Everything is fixed now. Feb 20 '19 at 20:23

For the variance, you need to evaluate $$E[X^T X]^2$$ and $$E[(X^T X)^2]$$.

For the former: $$E[X^T X] = \operatorname{tr} E[X^T X] = \operatorname{tr} E[X X^T] = \operatorname{tr} \Sigma$$

For the latter, using Isserlis' theorem: \begin{aligned} &E[(X^T X)^2] = \sum_{ij} E[X_i^2 X_j^2] \\ &= \sum_{ij} \bigl\{E[X_i X_i] \, E[X_j X_j] + 2 \, E[X_i X_j] \, E[X_i X_j]\bigr\} \\ &= \sum_{ij} \bigl\{\Sigma_{ii} \, \Sigma_{jj} + 2 \, \Sigma_{ij}^2\bigr\} \\ &= (\operatorname{tr} \Sigma)^2 + 2 \operatorname{tr} \Sigma^2 \end{aligned}

Hence $$\operatorname{Var}[X^T X] = 2 \operatorname{tr}\Sigma^2 = 2 \sum_{i=1}^{d} \lambda_i^2$$, i.e. twice the sum of the squared eigenvalues.

• Consider the case $d = 2$ and $\sigma_{1, 2} = 0$ (independence). Then, $\mathbb{E}( (X_1^2 + X_2^2)^2) = \mathbb{E}(X_1^4 + 2 X_1 X_2 + X_2^4) = 3(\sigma_{1, 1}^2 + \sigma_{2, 2}^2) + 2 \sigma_{1, 1}\sigma_{2, 2}$. You are missing the power 4 of the Gaussians (that gives the factor 3). Feb 20 '19 at 20:28
• The power of four is included in the sum when $i=j$, i.e. $E[X^4] = 3\sigma^4$.
– user114668
Feb 20 '19 at 20:33
• Up to the convention of $\sigma$ v.s. $\sigma^2$ in the covariance matrix, I am convinced that the Wick/Isserlis formula is true. What I say is that you should get a $3$ at some point. Make the case $d = 2$ with this formula and compare the results. Or find the mistake in my proof ;) Feb 20 '19 at 20:43
• As per my above comment, take $\Sigma = I_d$, your result does not give $2d$ as for a chi-squared distribution.
– user114668
Feb 20 '19 at 20:59
• You were right again ! :) Well, partitions that index two-dimensional indices are trickier than expected. In any case, this deserves an upvote. Feb 21 '19 at 14:00