Return to Question

Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $\|x\|_{\Lambda^{-1}} :=\|\Lambda^{-1/2} x\|_2 = \sqrt{x^\top \Lambda^{-1} x}$, and define the Gaussian width of $S$, denoted $\omega(S)$, by $$ \omega(S):= \mathbb E_z \left[\sup_{x \in S}x^\top z\right], $$

where the coordinates of $z$ is a standard Gaussian random vector in $\mathbb R^n$. It is clear that $$ \begin{split} \omega(S) &\le \mathbb E_z \sup_{\|x\|_2 \le R} x^\top z = R\cdot \mathbb E\,\|z\|_2 \lesssim R\sqrt{n},\\ \omega(S) &\le \mathbb E_z\sup_{\|\Lambda^{-1/2} x\|_2\le 1} x^\top z = \mathbb E_z \sup_{\|y\|_2 \le 1}y^\top \Lambda^{1/2} z = \mathbb E \|\Lambda^{1/2} z\|_2 \lesssim \sqrt{\mbox{trace}(\Lambda)}. \end{split} $$

Putting things together, we obtain that $$ \omega(S) \lesssim \min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right), \tag{1} $$

Question. Is it possible to choose $\Lambda$ (and $R$) such that $\omega(S)$ is very much less than $\min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right)$ in the limit $n \to \infty$ ?

Note that such a $\Lambda$ must necessarily be badly condition in the sense that if $\lambda_1$ (resp. $\lambda_n$) is the largest (resp. smallest) eigenvalue of $\Lambda$, then we can't have $$ c \le \lambda_n \le \lambda_1 \le C, \tag{2} $$ for some absolute positive constant $c$ and $C$. Indeed, otherwise let $g := \min(R,\sqrt{\lambda_n})z/\|z\|_2$. Then, $g \in S$ by construction, and so

$$ \begin{split} \omega(S) &\ge \mathbb E_z\, g^\top z = \min(R,\sqrt{\lambda_n})\mathbb E_z\,\|z\|_2 \gtrsim \min(R,\sqrt{\lambda_n})\sqrt{n}\\ & \gtrsim \min(R,\sqrt{c})\sqrt{n} \gtrsim \min(R,1)\sqrt{n}. \end{split} $$ We conclude that $\omega(S) \gtrsim \min(R,1)\sqrt n$ under Condition (2), which matches the upper-bound (1).

Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $\|x\|_{\Lambda^{-1}} :=\|\Lambda^{-1/2} x\|_2 = \sqrt{x^\top \Lambda^{-1} x}$, and define the Gaussian width of $S$, denoted $\omega(S)$, by $$ \omega(S):= \mathbb E_z \left[\sup_{x \in S}x^\top z\right], $$

where $z$ is a standard Gaussian random vector in $\mathbb R^n$. It is clear that $$ \begin{split} \omega(S) &\le \mathbb E_z \sup_{\|x\|_2 \le R} x^\top z = R\cdot \mathbb E\,\|z\|_2 \lesssim R\sqrt{n},\\ \omega(S) &\le \mathbb E_z\sup_{\|\Lambda^{-1/2} x\|_2\le 1} x^\top z = \mathbb E_z \sup_{\|y\|_2 \le 1}y^\top \Lambda^{1/2} z = \mathbb E \|\Lambda^{1/2} z\|_2 \lesssim \sqrt{\mbox{trace}(\Lambda)}. \end{split} $$

Putting things together, we obtain that $$ \omega(S) \lesssim \min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right), \tag{1} $$

Question. Is it possible to choose $\Lambda$ (and $R$) such that $\omega(S)$ is very much less than $\min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right)$ in the limit $n \to \infty$ ?

Note that such a $\Lambda$ must necessarily be badly condition in the sense that if $\lambda_1$ (resp. $\lambda_n$) is the largest (resp. smallest) eigenvalue of $\Lambda$, then we can't have $$ c \le \lambda_n \le \lambda_1 \le C, \tag{2} $$ for some absolute positive constant $c$ and $C$. Indeed, otherwise let $g := \min(R,\sqrt{\lambda_n})z/\|z\|_2$. Then, $g \in S$ by construction, and so

$$ \begin{split} \omega(S) &\ge \mathbb E_z\, g^\top z = \min(R,\sqrt{\lambda_n})\mathbb E_z\,\|z\|_2 \gtrsim \min(R,\sqrt{\lambda_n})\sqrt{n}\\ & \gtrsim \min(R,\sqrt{c})\sqrt{n} \gtrsim \min(R,1)\sqrt{n}. \end{split} $$ We conclude that $\omega(S) \gtrsim \min(R,1)\sqrt n$ under Condition (2), which would match the upper-bound (1).

Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $\|x\|_{\Lambda^{-1}} :=\|\Lambda^{-1/2} x\|_2 = \sqrt{x^\top \Lambda^{-1} x}$, and define the Gaussian width of $S$, denoted $\omega(S)$, by $$ \omega(S):= \mathbb E_z \left[\sup_{x \in S}x^\top z\right], $$

where the coordinates of $z$ is a standard Gaussian random vector in $\mathbb R^n$. It is clear that $$ \begin{split} \omega(S) &\le \mathbb E_z \sup_{\|x\|_2 \le R} x^\top z = R\cdot \mathbb E\,\|z\|_2 \lesssim R\sqrt{n},\\ \omega(S) &\le \mathbb E_z\sup_{\|\Lambda^{-1/2} x\|_2\le 1} x^\top z = \mathbb E_z \sup_{\|y\|_2 \le 1}y^\top \Lambda^{1/2} z = \mathbb E \|\Lambda^{1/2} z\|_2 \lesssim \sqrt{\mbox{trace}(\Lambda)}. \end{split} $$

Putting things together, we obtain that $$ \omega(S) \lesssim \min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right), \tag{1} $$

Question. Is it possible to choose $\Lambda$ (and $R$) such that $\omega(S)$ is very much less than $\min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right)$ in the limit $n \to \infty$ ?

Note that such a $\Lambda$ must necessarily be badly condition in the sense that if $\lambda_1$ (resp. $\lambda_n$) is the largest (resp. smallest) eigenvalue of $\Lambda$, then we can't have $$ c \le \lambda_n \le \lambda_1 \le C, \tag{2} $$ for some absolute positive constant $c$ and $C$. Indeed, otherwise let $g := \min(R,1/\sqrt{\lambda_1})z/\|z\|_2$. Then, $g \in S$ by construction, and so

$$ \begin{split} \omega(S) &\ge \mathbb E_z\, g^\top z = \min(R,\sqrt{\lambda_n})\mathbb E_z\,\|z\|_2 \gtrsim \min(R,\sqrt{\lambda_n})\sqrt{n}\\ & \gtrsim \min(R,\sqrt{c})\sqrt{n} \gtrsim \min(R,1)\sqrt{n}. \end{split} $$ We conclude that $\omega(S) \gtrsim \min(R,1)\sqrt n$ under Condition (2), which matches the upper-bound (1).

Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $\|x\|_{\Lambda^{-1}} :=\|\Lambda^{-1/2} x\|_2 = \sqrt{x^\top \Lambda^{-1} x}$, and define the Gaussian width of $S$, denoted $\omega(S)$, by $$ \omega(S):= \mathbb E_z \left[\sup_{x \in S}x^\top z\right], $$

where the coordinates of $z$ is a standard Gaussian random vector in $\mathbb R^n$. It is clear that $$ \begin{split} \omega(S) &\le \mathbb E_z \sup_{\|x\|_2 \le R} x^\top z = R\cdot \mathbb E\,\|z\|_2 \lesssim R\sqrt{n},\\ \omega(S) &\le \mathbb E_z\sup_{\|\Lambda^{-1/2} x\|_2\le 1} x^\top z = \mathbb E_z \sup_{\|y\|_2 \le 1}y^\top \Lambda^{1/2} z = \mathbb E \|\Lambda^{1/2} z\|_2 \lesssim \sqrt{\mbox{trace}(\Lambda)}. \end{split} $$

Putting things together, we obtain that $$ \omega(S) \lesssim \min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right), \tag{1} $$

Question. Is it possible to choose $\Lambda$ (and $R$) such that $\omega(S)$ is very much less than $\min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right)$ in the limit $n \to \infty$ ?

Note that such a $\Lambda$ must necessarily be badly condition in the sense that if $\lambda_1$ (resp. $\lambda_n$) is the largest (resp. smallest) eigenvalue of $\Lambda$, then we can't have $$ c \le \lambda_n \le \lambda_1 \le C, \tag{2} $$ for some absolute positive constant $c$ and $C$. Indeed, otherwise let $g := \min(R,\sqrt{\lambda_n})z/\|z\|_2$. Then, $g \in S$ by construction, and so

$$ \begin{split} \omega(S) &\ge \mathbb E_z\, g^\top z = \min(R,\sqrt{\lambda_n})\mathbb E_z\,\|z\|_2 \gtrsim \min(R,\sqrt{\lambda_n})\sqrt{n}\\ & \gtrsim \min(R,\sqrt{c})\sqrt{n} \gtrsim \min(R,1)\sqrt{n}. \end{split} $$ We conclude that $\omega(S) \gtrsim \min(R,1)\sqrt n$ under Condition (2), which matches the upper-bound (1).

Let $\Lambda$ be a positive-definite matrix of size $n$ such that $\mbox{trace}(\Lambda) = 1$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $\|x\|_{\Lambda^{-1}} :=\|\Lambda^{-1/2} x\|_2 = \sqrt{x^\top \Lambda^{-1} x}$, and define the Gaussian width of $S$, denoted $\omega(S)$, by $$ \omega(S):= \mathbb E_z \left[\sup_{x \in S}x^\top z\right], $$

where the coordinates of $z$ is a standard Gaussian random vector in $\mathbb R^n$. It is clear that $$ \begin{split} \omega(S) &\le \mathbb E_z \sup_{\|x\|_2 \le R} x^\top z = R\cdot \mathbb E\,\|z\|_2 \lesssim R\sqrt{n},\\ \omega(S) &\le \mathbb E_z\sup_{\|\Lambda^{-1/2} x\|_2\le 1} x^\top z = \mathbb E_z \sup_{\|y\|_2 \le 1}y^\top \Lambda^{1/2} z = \mathbb E \|\Lambda^{1/2} z\|_2 \lesssim \sqrt{\mbox{trace}(\Lambda)}. \end{split} $$

Putting things together, we obtain that $$ \omega(S) \lesssim \min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right), \tag{1} $$

Question. Is it possible to choose $\Lambda$ such that $\omega(S)$ is very much less than $\min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right)$ in the limit $n \to \infty$ ?

Note that such a $\Lambda$ must necessarily be badly condition in the sense that if $\lambda_1$ (resp. $\lambda_n$) is the largest (resp. smallest) eigenvalue of $\Lambda$, then we can't have $$ c \le \lambda_n \le \lambda_1 \le C, \tag{2} $$ for some absolute positive constant $c$ and $C$. Indeed, otherwise let $g := \min(R,1/\sqrt{\lambda_1})z/\|z\|_2$. Then, $g \in S$ by construction, and so

$$ \begin{split} \omega(S) &\ge \mathbb E_z\, g^\top z = \min(R,\sqrt{\lambda_n})\mathbb E_z\,\|z\|_2 \gtrsim \min(R,\sqrt{\lambda_n})\sqrt{n}\\ & \gtrsim \min(R,\sqrt{c})\sqrt{n} \gtrsim \min(R,1)\sqrt{n}. \end{split} $$ We conclude that $\omega(S) \gtrsim \min(R,1)\sqrt n$ under Condition (2), which matches the upper-bound (1).

Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $\|x\|_{\Lambda^{-1}} :=\|\Lambda^{-1/2} x\|_2 = \sqrt{x^\top \Lambda^{-1} x}$, and define the Gaussian width of $S$, denoted $\omega(S)$, by $$ \omega(S):= \mathbb E_z \left[\sup_{x \in S}x^\top z\right], $$

where the coordinates of $z$ is a standard Gaussian random vector in $\mathbb R^n$. It is clear that $$ \begin{split} \omega(S) &\le \mathbb E_z \sup_{\|x\|_2 \le R} x^\top z = R\cdot \mathbb E\,\|z\|_2 \lesssim R\sqrt{n},\\ \omega(S) &\le \mathbb E_z\sup_{\|\Lambda^{-1/2} x\|_2\le 1} x^\top z = \mathbb E_z \sup_{\|y\|_2 \le 1}y^\top \Lambda^{1/2} z = \mathbb E \|\Lambda^{1/2} z\|_2 \lesssim \sqrt{\mbox{trace}(\Lambda)}. \end{split} $$

Putting things together, we obtain that $$ \omega(S) \lesssim \min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right), \tag{1} $$

Question. Is it possible to choose $\Lambda$ (and $R$) such that $\omega(S)$ is very much less than $\min\left(R\sqrt n,\sqrt{\mbox{trace}(\Lambda)}\right)$ in the limit $n \to \infty$ ?

Note that such a $\Lambda$ must necessarily be badly condition in the sense that if $\lambda_1$ (resp. $\lambda_n$) is the largest (resp. smallest) eigenvalue of $\Lambda$, then we can't have $$ c \le \lambda_n \le \lambda_1 \le C, \tag{2} $$ for some absolute positive constant $c$ and $C$. Indeed, otherwise let $g := \min(R,1/\sqrt{\lambda_1})z/\|z\|_2$. Then, $g \in S$ by construction, and so

$$ \begin{split} \omega(S) &\ge \mathbb E_z\, g^\top z = \min(R,\sqrt{\lambda_n})\mathbb E_z\,\|z\|_2 \gtrsim \min(R,\sqrt{\lambda_n})\sqrt{n}\\ & \gtrsim \min(R,\sqrt{c})\sqrt{n} \gtrsim \min(R,1)\sqrt{n}. \end{split} $$ We conclude that $\omega(S) \gtrsim \min(R,1)\sqrt n$ under Condition (2), which matches the upper-bound (1).