3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.