6
$\begingroup$

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!

$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice! Only I don't see how and why you would use Paley--Zygmund, instead of just writing $E(a\cdot X)^2\,1_{\|X\|>\sqrt n}\le E\|X\|^2\,1_{\|X\|>\sqrt n}\to0$ as $n\to\infty$, for any unit vector $a$. $\endgroup$ – Iosif Pinelis Mar 22 '19 at 14:26
  • $\begingroup$ I wanted to compare 2nd with 4th moment. But yes there is a simpler argument along the lines you suggest, I will include it. $\endgroup$ – Guillaume Aubrun Mar 22 '19 at 14:34
  • $\begingroup$ Do you define $\tilde{Y}:=\text{E}(YY^T)^{-\frac{1}{2}}Y?$ If yes, could you explain how to get that $\lVert \langle \tilde{Y},\theta \rangle \rVert_{\psi_2}\leq 2C$ for all unit vectors $\theta$ holds. $\endgroup$ – Hugo10T Aug 15 at 12:56
  • $\begingroup$ Yes $\tilde{Y} = T^{-1/2}(Y)$ for $T=\mathbf{E} [ YY^T]$. Now, observe that $\langle \tilde{Y}, \theta \rangle$ is the same as $\langle Y, T^{-1/2} \theta \rangle$ and therefore $\| \langle \tilde{Y}, \theta \rangle \|_{\psi_2} \leq C \|T^{-1/2} \theta \| \leq \sqrt{2}C$. $\endgroup$ – Guillaume Aubrun Aug 24 at 8:15
0
$\begingroup$

This conjecture is false. Indeed, let, as in your example, $X$ be uniformly distributed on $\{-1,1\}^n$. Let $Y$ be a random vector uniformly distributed on the set $$S_Y:=\{\sqrt n\,e_1,-\sqrt n\,e_1,\dots,\sqrt n\,e_n,-\sqrt n\,e_n\},$$ where $(e_1,\dots,e_n)$ is the standard basis of $\mathbb R^n$. Then $EYY^T=I_n=EXX^T$. Also, $\|Y\|=\sqrt n=\|X\|$, where $\|\cdot\|$ is the Euclidean norm, so that $Y$ is sub-Gaussian in exactly the same sense as $X$ is. However, $|S_Y|=2n=o(e^{an})$ as $n\to\infty$ for any constant $a>0$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I think the OP means by subgaussian that all 1-dimensional marginals of $X$ have to be (uniformly) subgaussian $\endgroup$ – Guillaume Aubrun Mar 22 '19 at 12:52
  • $\begingroup$ @GuillaumeAubrun : Where do you see any hint about or any mentioning of one-dimensional marginals? Rather to the contrary, in the description of the example in the OP only the constant norm of $X$ is mentioned. $\endgroup$ – Iosif Pinelis Mar 22 '19 at 13:11
  • $\begingroup$ I've seen this terminology used by people working in high-dimensional probability/convex geometry $\endgroup$ – Guillaume Aubrun Mar 22 '19 at 13:29
  • $\begingroup$ But why do you think that usage would apply here, especially given that in the description of the example in the OP only the constant norm of $X$ is mentioned? $\endgroup$ – Iosif Pinelis Mar 22 '19 at 13:33
  • 1
    $\begingroup$ I am sorry that I didn't give the definition of $\|\cdot\|_{\psi_2}$ of a random vector. It has the same meaning as @Guillaume Aubrun said. I have added it in the question. $\endgroup$ – zbh2047 Mar 22 '19 at 13:48

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.