Skip to main content
2 of 2
added 59 characters in body
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

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.

dohmatob
  • 6.9k
  • 1
  • 18
  • 76