I would like to dig deeper into the problem posted Probability that a convex shape contains the unit ball:

If you pick n points uniformly at random from the surface of a d dimensional sphere of radius r>1 with center at the origin, what is the probability that the convex hull of these points contains the unit ball (of dimension d) centered at the origin?

In the comment session I saw an exponential lower bound:

...for $\ell_2^d$ to well-embed into $\ell_\infty^m$ the dimension $m$ must be exponential in $d$...$m$ is at least $\exp(d/(64r^2))$... Saying that the convex symmetric hull of $n$ points can contain the unit ball is the same as saying that $\ell_2^d$ embeds into $\ell_\infty^m$ with distortion at most $r$.

I also came across Smallest singular value of random matrices and geometry of random polytopes. They consider a random matrix $\Gamma\in\mathbb{R}^{m\times d}$ where each entry is an i.i.d Gaussian. Let $K_m$ be the absolute convex hull of the rows of $\Gamma$, in theorem 4.2 and the following remark, they stated (I paraphrased) that:

If $m$ is polynomial in $d$, then $P(K_m\supset C\sqrt{\beta\ln(m/d)}B_2^d)\geq1-\exp(-cd^\beta m^{1-\beta})$

These two statements somehow seem a little conflicting. The first statement says that you need exponentially many points in d to make the convex hull include a $\ell_2$ ball, while the second says only polynomially many would make the convex hull $K_m$ include a $\ell_2$ ball with high probability.

My understanding is that, if we write $\Gamma$ as the embedding, in the first statement, the row vector of $\Gamma$ is picked on a sphere, which is bounded, so it is harder to contain a $\ell_2$ ball, while in the second statement, we sample rows according to Gaussian, which is unbounded, so it's easier to contain a ball. Note that in both statement, we can control how large the included ball is.

If I understand correctly, Asymptotic shape of a random polytope in a convex body theorem 1.1 says that if each row of $\Gamma$ is uniformly picked in a ball, and if $m$ is only polynomial in $d$, then the best we can say is with high probability, $K_m$ contains a $\ell_2$ ball (the paper gives inclusion of $L_q$ centroid $Z_q$, but a scaled $\ell_2$ ball is included in $Z_q$ if $q>2$), but we can't describe how large the ball is, unless we make $m$ exponential in $d$, as stated by the first statemenet.

Thanks for any advice!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.