Proving Sub-Gaussian Random Vector Implies Exponentially Large $|S|$

pr.probability

Let $X$ be an isotropic random vector (i.e. $E[XX^T]=I_n$) and $X$ takes value in a finite set $S \subset\mathbb R^n$. If $X$ is a sub-Gaussian random vector and the norm $\|X\|_{\psi_2}\le C$ where $C$ is a constant, it will imply that $S$ is expoentially large with dimension $n$.

Note that $X$ is said to be sub-Gaussian with norm $K$ iff the marginal distribution in any direction is a sub-Gaussian with norm less or equal than $K$.

For example, if $X$ is uniformly distributed in $\{-1,+1\}^n$, then $X$ is a sub-Gaussian random vector with constant norm but now $|S|=2^n$. (It can be proved)

How can I prove the proposition? I just have no idea to deal with the "exponential" proof. Thank you!

Best Answer

If $(Z_i)_{1 \leq i \leq N}$ are scalar random variables with $\|Z_i\|_{\Psi_2} \leq C$, then $\mathbf{E} \max Z_i \leq CC'\sqrt{\log N}$ by the usual union bound argument.

Now let $X$ be an isotropic random vector in $\mathbf{R}^n$ such that $\|\langle X,\theta \rangle \|_{\Psi_2} \leq C $ for every unit vector $\theta$, and let $S$ be the support of $X$. Choose a number $A$ such that $S$ is contained in the ball of radius $A\sqrt{n}$. Since (denoting by $\|\cdot\|$ the Euclidean norm) $$ ||X||^2 \leq \sup_{x \in S} |\langle X,x\rangle|, $$ it follows from the aforementioned estimate that $$ n = \mathbf{E} ||X||^2 \leq A \sqrt{n} CC'\sqrt{\log |S|}.$$ In particular, we get $|S| \geq \exp(c(A,C) n)$.

We are going to reduce to the situation where $A$ is bounded. To that end, take an isotropic subgaussian random vector $X$ with $||\langle X,\theta \rangle||_{\Psi_2} \leq C$. This implies in particular $\mathbf{E} \langle X,\theta \rangle^4 \leq 4C^2$ (possibly change $4$ into another number depending on which definition of $\|\cdot\|_{\psi_2}$ you use). Define a new random vector as $Y = X {\bf 1}_{\{ ||X|| \leq 4C \sqrt{n}\} }$. The vector $Y$ is not exactly isotropic but satisfies $\frac 12 I_n \leq \mathbf{E} YY^T \leq I_n$. This is because (by Cauchy-Schwarz and Markov inequalities) $$ \mathbf{E} \left[ \langle X,\theta \rangle^2 {\bf 1}_{\{||X|| > 4C \sqrt{n}\}} \right] \leq \left( \mathbf{E} \left[ \langle X,\theta \rangle^4 \right] \cdot \mathbf{P}(||X||^2 > 16C^2n)\right)^{1/2} \leq \sqrt{\frac{4C^2}{16C^2}} = \frac{1}{2}$$

We are now going to apply the first part of the argument to a linear image $\tilde{Y}$ of $Y$ which is isotropic. The random vector $\tilde{Y}$ is supported in the ball of radius $A\sqrt{n}$ for $A=8C$, and satisfies $\|\langle \tilde{Y},\theta \rangle \|_{\Psi_2} \leq 2C$, so the support of $Y$ (which is contained into $S \cup \{0\}$) contains at least $\exp(c(8C,2C)n)$ points.

Related Question