Skip to main content
1 of 2
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

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

Let $n$ be a large positive integer and fix $r \ge 0$. Set $S := B_2^n \cap [-r,r]^n$, where $B_2^n$ is the euclidean unit-ball in $\mathbb R^n$. 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_n)$.

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

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

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

dohmatob
  • 6.9k
  • 1
  • 18
  • 76