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$

2 Answers 2

4
$\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$
5
  • $\begingroup$ Thanks! I think I need $var(Y) = O(d) = o(d^2)$, and that should be achieved by your derivation. $\endgroup$ Commented Aug 15, 2017 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
    Commented Aug 18, 2017 at 0:38
  • $\begingroup$ Ah I just know how to do it. Thanks! $\endgroup$ Commented Aug 18, 2017 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$
    – user114668
    Commented Feb 18, 2019 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
    Commented Feb 20, 2019 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$
5
  • $\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
    Commented Feb 20, 2019 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$
    – user114668
    Commented Feb 20, 2019 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
    Commented Feb 20, 2019 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$
    – user114668
    Commented Feb 20, 2019 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
    Commented Feb 21, 2019 at 14:00

You must log in to answer this question.

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