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

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

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

Note. Using Proposition 1 of this manuscript with $T = [-1/\sqrt{d},1/\sqrt{d}]^n$,$T = [-1/\sqrt{d},1/\sqrt{d}]^d$ $m=2d$(the convex hull of $m=2^d$ points in $B_2^d$), and $s=1/(r\sqrt{n})$$s=1/(r\sqrt{d})$, 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}. $$$$ \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.

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.

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.

Source Link
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.