# Gaussian width of intersection of cube and ball in high-dimensional euclidean space

Let $$d$$ be a large positive integer and fix $$r \ge 0$$. Set $$S := B_2^n \cap [-r,r]^d$$, where $$B_2^d$$ is the euclidean unit-ball in $$\mathbb R^d$$. Finally, let $$\omega(S)$$ be the Gaussian width of $$S$$, defined by

$$\omega(S) := \mathbb E \sup_{x \in S} x^\top z,$$

where the expectation is over $$z \sim N(0,I_d)$$.

Question. What is a good upper-bound for $$\omega(T)$$, valid for large $$d$$ ?

Note. Using Proposition 1 of this manuscript with $$T = [-1/\sqrt{d},1/\sqrt{d}]^d$$ (the convex hull of $$m=2^d$$ points in $$B_2^d$$), and $$s=1/(r\sqrt{d})$$, I'm able to obtain the following upper-bound $$\omega(S) = s\cdot\omega(s B_2^d \cap T) \lesssim r\sqrt{d\log(em)} \land \sqrt{d} = rd \land \sqrt{d}.$$

Unfortunately, the above bound is not very good for my purposes.

The answer is, up to a constant factor $$\omega(S) = \Theta(\min(\sqrt{d}, rd))$$.
To see the upper bound, we can use the fact that if $$S \subset Q$$, then $$\omega(S) \leq \omega(Q)$$, therefore $$\omega(B_2^n \cap r B_\infty^n) \leq \min(\omega(B_2^n), r \omega(B_\infty^n)) = \min( \mathbb{E}_{z \sim \mathcal{N}(0, I)} \|z\|_2, r\, \mathbb{E}_{z \sim \mathcal{N}(0, I)} \|z\|_1) = \mathcal{O}(\min(\sqrt{d}, rd)).$$
For the lower bound, note that for any given vector $$z$$, we can chose $$\tilde{z} \in S$$ to be $$\tilde{z}_i := \min(1/\sqrt{d}, r) \mathrm{sgn}(z_i)$$. With this choice, we have for any fixed $$z$$ $$\sup_{x \in S} x^T z \geq \tilde{z}^T z = \min(1/\sqrt{d}, r) \sum_i |z_i| = \min(1/\sqrt{d}, r) \|z\|_1,$$ and therefore $$\omega(S) \geq \min(1/\sqrt{d}, r) \mathbb{E}_{z\sim\mathcal{N}(0, I)} \|z\|_1 = \Omega(\min(\sqrt{d}, rd)$$.
Note that this is not inconsistent with the upper bound given by Proposition 1 in the cited paper --- the hypercube $$[-r, r]^d$$ has $$2^d$$ vertices, not $$2d$$.
• Thanks. I see where my error came from. My $T=[-1/\sqrt{d},1/\sqrt{d}]^d$ is not the convex hull of $m=2d$ but $m=2^d$, points in $B_2^d$. Then, $\log(em) \asymp d$ and not $\sqrt{d}$ as I carelessly thought. Commented Oct 7, 2022 at 21:18