# Tight upper-bounds for the Gaussian width of intersection of intersection of hyper-ellipsoid and unit-ball

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

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