Inner radius of a random convex hull

Question

Let $\sigma_1,\ldots,\sigma_M$ i.i.d. random vectors in $\mathbb{R}^d$, and for notational convenience, let $\Sigma=(\sigma_1,\ldots,\sigma_M)$. I am interested in understanding $$ \gamma(\Sigma) = \min_{\lambda\in\Delta_M} \Big\|\sum_{i=1}^M \lambda_i \sigma_i\Big\|_2, $$ where $\Delta_M=\{\lambda \in\mathbb{R}_+^M: \sum_i \lambda_i=1\}$, is the $M$-dimensional simplex. I am primarily interested in the cases of the distribution being the standard Gaussian and the uniform probability on the hypercube $\{-1,+1\}^d$.

Here is what I know:

1. If we consider continuous distributions, the sigmas are linearly independent with probability 1 when $M\leq d$, thus this quantity should be strictly positive in this regime. In the discrete case, the latter claim should still hold with high probability.
2. For the discrete case, the function $\gamma(\cdot)$ is Lipschitz for the Hamming distance, so it concentrates around its mean
3. Similarly, for the Gaussian case one can prove $\gamma(\cdot)$ is Lipschitz for the Euclidean norm (more precisely, the Frobenius norm of $\Sigma$ as a matrix), so it concentrates around its mean.

By the last two observations, I am now mostly interested in understanding $\mathbb{E}_{\Sigma}[\gamma(\Sigma)]$, as a function of $M$. Clearly, for $M=1$, and for my distributions of interest, $\mathbb{E}[\gamma]=\sqrt{d}$, and I believe that for $M>d$, $\mathbb{E}[\gamma]\approx0$ (although I don't have a proof).

My question is how to compute (or lower bound) this expectation as a function of $M$. Connections with the literature are also welcome. As a final comment, I tried to lower bound the expectation using the Khintchine inequality, but the minimum in between seems to ruin the approach.

PS: $\gamma(\Sigma)$ represents the largest possible (origin centered) ball not touching the simplex generated by the vectors $\sigma_1,\ldots,\sigma_M$; which is similar, but not equivalent to the inner radius of the (symmetrized) convex hull. So better suggestions for a title are also welcome.

Answer 1

This is not a direct reply, except possibly to your invitation that "Connections with the literature are also welcome." I wonder if just understanding the metric properties of random simplices might help, for your $\Delta_M$ are particular "random" simplices? If so, perhaps this is relevant:

Kobayashi, Kenta. "A Recursive Formula for the Circumradius of the $n$-Simplex." In Forum Geometricorum, vol. 16, pp. 179-184. 2016. (PDF download.)

Abstract. We present a recursive formula which gives the circumradius of the $n$-simplex in terms of the circumradius of its facets. ... We could only prove the formula for $n \le 5$, but numerical results strongly suggest that our formula holds true for any $n$.

---

         

---

This negative result might narrow your options:

Vatne, Jon Eivind. "Simplices rarely contain their circumcenter in high dimensions." Applications of Mathematics 62, no. 3 (2017): 213-223.

Abstract. ... In a natural probability measure on the set of $n$-dimensional simplices, we show that the probability that a uniformly random $n$-simplex contains its circumcenter is $1/2^n$.

Note that both references I cite are quite recent (2016, 2017), so perhaps this is a developing area of investigation.

Answer 2

I was able to compute a nontrivial lower bound for the Gaussian case (thanks to Ying Xiao who privately proposed the approach). For convenience I will consider the distribution of $\sigma_1\sim{\cal N}(0,\frac1d I)$. Now, I will ignore the nonnegativity constraints on $\lambda$ and consider the following Lagrangian $$ {\cal L}(\lambda,\mu) = \|\Sigma \lambda\|_2^2-2\mu (\mathbf{1}^{\top}\lambda-1).$$ Writing the first-order optimality conditions, we get \begin{eqnarray*} \lambda^{\ast} &=& \mu^{\ast}(\Sigma^{\top}\Sigma)^{-1}\mathbf{1}\\ \mu^{\ast} &=& \dfrac{1}{\mathbf{1}^{\top}(\Sigma^{\top}\Sigma)^{-1}\mathbf{1}}. \end{eqnarray*}

This way $\|\Sigma\lambda^{\ast}\|_2^2=1/[\mathbf{1}^{\top}(\Sigma^{\top}\Sigma)^{-1}\mathbf{1}]$. Therefore, the quantity of interest can be lower bounded by $$\mathbb{E}[\|\Sigma\lambda^{\ast}\|_2]=\mathbb{E}\Big[\frac{1}{\sqrt{\mathbf{1}^{\top}(\Sigma^{\top}\Sigma)^{-1}\mathbf{1}}}\Big].$$ The term inside the expectation squared is known to have a chi-squared distribution with $d-M+1$ degrees of freedom (I found out about this here), thus the expectation above is of order $\sqrt{\frac{d-M+1}{d}}$.

I believe something similar should be true for the (scaled) Boolean distribution. On the other hand, I don't know how tight is this lower bound, but it turns out it suffices for my problem.

Answer 3

What you want looks like very much the "Uniform Uncertainty Principle" in this paper of Candes and Tao https://statweb.stanford.edu/~candes/papers/OptimalRecovery.pdf which is proved for both Bernoulli or Gaussian random vectors.