1
$\begingroup$

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).

$\endgroup$

1 Answer 1

1
$\begingroup$

Disclaimer: After a bit of work, I've come up with the following example. Happy to hear about others.


Fix $\beta \in (1,\infty)$, and for any integer $n \ge 1$, let $\lambda_n = n^{-\beta}$, and let $\Lambda = \Lambda(n)$ be the $n \times n$ diagonal matrix with diagonal entries $\lambda_1,\ldots,\lambda_n$. We refer to this model for $\Lambda$ as $\beta$-polynomial.

Thanks to Example 4 of this paper From Gauss to Kolmogorov: Localized Measures of Complexity for Ellipses , we know that $w(S) \asymp R^{1-1/\beta}$. On the other hand, one computes $\min(R\sqrt{n},\sqrt{\mbox{trace}(\Lambda)}) \asymp \min(R\sqrt{n},1)$. We deduce that,

If $n^{-\beta/2} \ll R \lesssim n^{-1/2}$, then $$ \frac{\omega(S)}{\min(R\sqrt{n},\sqrt{\mbox{trace}(\Lambda)})} \asymp \frac{R^{1-1/\beta}}{R\sqrt{n}} = \frac{1}{R^{1/\beta}\sqrt n} \ll 1. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.