Does Approx Carathéodory's theorem implies dimensionality reduction

Question

Carathéodory's theorem says that if a point $x$ of $R^d$ lies in the convex hull of a point set $P$, then there is a subset $P′ \subseteq P$ consisting of $d + 1$ or fewer points such that $x$ can be expressed as a convex combination of $P′$.

A recent result by Barman (see paper) shows an approximate version of the above theorem. More precisely, given a set of points $P$ in the $p$-unit ball with norm $p \in [2,\infty)$, then for every point $x$ in the convex hull of $P$ there exists an $\epsilon$-close point $x'$ (under the $p$-norm distance) that can be expressed as a convex combination of $O\left(\frac{p}{\epsilon^2} \right)$ many points of P.

Now, my question is that does the above result implies (or have some connection with) some kind of dimensionality reduction for the points in the convex hull of $P$. It seems intuitive to me (however I don't have a formal proof of it) - as for any point $x$ inside the $P$ there is a point (say) $x'$ in a close neighborhood of $x$ which can be written as convex combination of constant many points of $P$, which in some sense dimensionality reduction of $x'$.

Pls let me know if I am able put my question clearly.

Thanks.

Answer 1

The approximate Caratheodory theorem goes back to the 60s, and probably way earlier than that (it follows for example from the mistake bound of the preceptron algorithm analysis). As for the dimensionality reduction, the answer is no - the supporting subsets are different subsets, and their number is too large. In particular, the number of possible subsets is $n^{O(1/\epsilon^2)}$ - but there is some connection...

Specifically, let $P$ be a set of $n$ points in high dimenionsional Euclidean space of diameter $1$. Let $Q$ be an $\epsilon$-net in the convex-hull of $P$. That is, any pair of points of $Q$ is in distance at least $\epsilon$ from each other, and every point of $CH(P)$ is in distance at most $\epsilon$ from some point of $Q$.

Now, by the approximate Caratheodory theorem, we know that $|Q| = n^{O(1/\epsilon^2)}$. Now, imagine that you do some experiment, and with probability half the experiment succeeds for half the points of $Q$ (or, more formally, half the pairs of $Q \times Q$ -- since we look on vectors formed by differences of points of $Q$). How many times do you have to repeat the experiment till all the points are served? Well, roughly $\log_2 |Q| = O(\epsilon^{-2} \log n)$, which is, surprise surprise, the target dimension in the JL lemma. This is of course, does not imply the JL lemma - it is somewhat of a "coincidence" - a wrong calculation that gives the right bounds...

There is a useful lesson here however - a set of $n$ points in high dimensions, induces roughly $n^{O(1/\epsilon^2)}$ points that are $\epsilon$-distinct, independent of the ambient dimension.