3
$\begingroup$

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$?

$\endgroup$
3
$\begingroup$

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 $.

$\endgroup$
  • $\begingroup$ Thanks! I think I need $var(Y) = O(d) = o(d^2)$, and that should be achieved by your derivation. $\endgroup$ – Koltchinskii Aug 15 '17 at 8:49
  • $\begingroup$ 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. $\endgroup$ – Synia Aug 18 '17 at 0:38
  • $\begingroup$ Ah I just know how to do it. Thanks! $\endgroup$ – Koltchinskii Aug 18 '17 at 21:17
  • $\begingroup$ 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$. $\endgroup$ – student Feb 18 at 11:34
  • $\begingroup$ 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. $\endgroup$ – Synia Feb 20 at 20:23
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Synia Feb 20 at 20:28
  • $\begingroup$ The power of four is included in the sum when $i=j$, i.e. $E[X^4] = 3\sigma^4$. $\endgroup$ – student Feb 20 at 20:33
  • $\begingroup$ 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 ;) $\endgroup$ – Synia Feb 20 at 20:43
  • $\begingroup$ As per my above comment, take $\Sigma = I_d$, your result does not give $2d$ as for a chi-squared distribution. $\endgroup$ – student Feb 20 at 20:59
  • $\begingroup$ You were right again ! :) Well, partitions that index two-dimensional indices are trickier than expected. In any case, this deserves an upvote. $\endgroup$ – Synia Feb 21 at 14:00

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.