I am trying to develop an intuition for the properties of the convex hull of a set of points in high ($d>20$) dimensions.

Consider a set of $n$ data points which are iid distributed according to some simple distribution (e.g. uniform hypercube, multivariate normal with mean $\mathbf{0}$ and identity covariance matrix $\mathbf{I}_d$, or similar). Now suppose we draw an $n+1$'th data point $\mathbf{x}$ from that same distribution. What can we say about the relationship between $\mathbf{x}$ and the convex hull of the first $n$ points?

My expectation$^1$ is that as dimensionality increases, the distance between $\mathbf{x}$ and the convex hull should grow for fixed $n$. I also expect the volume of the convex hull to, in some sense, shrink relative to the volume of the domain or something similar.

To make this more concrete, I would like some expression (or bound) on the expected distance between $\mathbf{x}$ and the convex hull for some simple data distribution as a function of $n$ and $d$.

Does such an example exist (either analytic or numeric) which could aid with my intuition?

Disclaimer: this is not my area of expertise, so even simple examples or half-answers would be very helpful.

$^1$ Inspired by section 2.5 of The Elements of Statistical Learning where the authors demonstrate the curse of dimensionality (e.g. points tend to be further apart as dimensions increase, side-length of the subcube needed to capture a fraction r of the volume of the data increases with dimension).

  • $\begingroup$ Perhaps the easiest upper bound on the expectation you can find is $E( \| X_{n+1} - \overline{X}_n\|_2 )$. Is this helpful? $\endgroup$ Commented Jan 17, 2022 at 18:53
  • 1
    $\begingroup$ Let $y^{(i)}$, $i=1,\dots, n$, be the first $n$ data points, and let $x$ be the subsequent data point. Draw each data point uniformly from a $d$ dimensional unit hypercube $[0,1]^d$. The probability that $x_j \geq \max_i y_j^{(i)}+1/2$ is $\int_{1/2}^1 dx_j (x_j-1/2)^n = \frac{1}{2^{n+1} (n+1)}$. The squared distance from $x$ to the convex hull of the $y$'s is at least $\sum_j \max\left(0,x_j - \max_i y_j^{(i)}\right)^2$. Each term of the sum is $>1/4$ with probability $\frac{1}{2^{n+1} (n+1)}$, so the sum has expectation $> \frac{d}{2^{n+3}(n+1)}$. $\endgroup$
    – Yly
    Commented Jan 18, 2022 at 8:28
  • $\begingroup$ @JoseAvilez This is along the lines of what I mentioned in the footnote but I would like to understand something about the nature of the convex hull rather than the fact that data becomes sparse and on the edge. $\endgroup$
    – Seraf Fej
    Commented Jan 18, 2022 at 14:06
  • $\begingroup$ @Yly this seems promising. If you could flesh this out into a complete answer it would be appreciated. I have only 20 hours left to award the bounty! $\endgroup$
    – Seraf Fej
    Commented Jan 18, 2022 at 14:08


You must log in to answer this question.