5
$\begingroup$

Given a multivariate normal random variable $X \sim \mathcal{N}(0, \Sigma_{d\times d})$, I am looking for an concentration bound of the following form:

$$\mathbb{P}( \|X\|_2 \leq C) \ge 1- \delta.$$

What can we have for $C$ here? I am thinking $C$ can be a polynomial of $d$, $\log(d/\delta)$ and other terms such as eigenvalues or trace of $\Sigma_{d\times d}$.

The closest I could find was if $\eta \sim \mathcal{N}(0, \Lambda^{-1})$, then $$\mathbb{P}( \|\eta\|_\Lambda \leq c \sqrt{d \log (d/\delta)} \ge 1 - \delta,$$ where $c$ is a constant.

$\endgroup$

1 Answer 1

5
$\begingroup$

From the properties of multivariate gaussian distribution, $X = \Sigma^{1/2} \xi$ for $\xi \sim \mathcal{N}\left(0, I_{d\times d}\right)$. As $\Sigma^{1/2}$ is symmetric, it can be decomposed as $\Sigma^{1/2} = Q \Lambda Q^T$, where $Q$ is orthogonal and $\Lambda$ is diagonal. Hence, $$ \mathbb{P}\left(\left\|X\right\|_2 \leq C^2\right) = \mathbb{P}\left(\left\|X\right\|_2^2 \leq C^2\right) = \mathbb{P}\left(\left\|Q \Lambda Q^T \xi\right\|_2^2 \leq C^2\right) = \mathbb{P}\left(\left\|\Lambda Q^T \xi\right\|_2^2 \leq C^2\right), $$ because orthogonal transformation preserves norm. Another property of standart gaussian distribution is that it's spherically symmetric: $Q \xi \overset{d}{=}\xi$ for any orthogonal matrix $Q$. So, $$\mathbb{P}\left(\left\|\Lambda Q^T \xi\right\|_2^2 \leq C^2\right) = \mathbb{P}\left(\left\|\Lambda\xi\right\|_2^2 \leq C^2\right),$$ as $Q^T$ is also orthogonal. Observe that $\left\|\Lambda\xi\right\|_2^2 = \sum_{i=1}^d \lambda_i^2 \xi_i^2$ is the sum of independent $\chi^2_1$-distributed variables with $\mathrm{E}\left(\left\|\Lambda\xi\right\|_2^2\right) = \sum_{i=1}^d \lambda_i^2 = \mathrm{Tr}(\Lambda^2) = \sum_{i=1}^d \mathrm{Var}(X_i)$. From Markov's inequality $$ \mathbb{P}\left(\left\|\Lambda\xi\right\|_2^2 \leq C^2\right) \geq 1 - \frac{1}{C^2} \cdot \mathrm{E}\left(\left\|\Lambda\xi\right\|_2^2\right), $$ so $\delta = \frac{1}{C^2} \cdot \mathrm{E}\left(\left\|\Lambda\xi\right\|_2^2\right) \Leftrightarrow C = \sqrt{\frac{1}{\delta} \sum_{i=1}^d \mathrm{Var}(X_i)} = \sqrt{\frac{1}{\delta} \mathrm{Tr}(\Sigma)}$.

$\endgroup$

You must log in to answer this question.

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