The Johnson-Lindenstrauss lemma implies that any set of $k$ points in $\mathbb{R}^d$ can be randomly projected into $d' \approx \log(k)/\epsilon^2$ dimensions such that the distances between each pair of points are approximately preserved, up to a multiplicative factor of $(1 \pm \epsilon)$. 


My question is whether such a projection will also approximately preserve convexity. Suppose the $k$ points lie on the surface of a convex body in $\mathbb{R}^d$. Does there exist a projection into $d'$ dimensions such that each point lies near the surface of a convex body? 



Do random projections (approximately) preserve convexity?
Yes, if the convex body is "sufficiently round". If it is not, the resulting "closeness" to the boundary of a convex set is in absolute terms rather than relative. I don't know whether it can be improved, but Bill Johnson's remarks suggest that it can't.


Let $X=\{x\_i\}$, $i=1,\dots,k$, be the set in question and $K$ the convex body whose boundary contains $X$. For normalization assume that $diam(K)=1$. For each $i$, let $y\_i$ be a point in $\mathbb R^d$ such that the vector $y\_i-x\_i$ is the unit inner normal to a supporting hyperplane to $K$ at $x\_i$. Then
$$
 \langle y\_i-x\_i, x\_j-x\_i \rangle \ge 0
$$
for all $j$ (the angle brackets denote the scalar product). Apply the Johnson-Lindenstrauss lemma to the set $X\cup\{y\_i\}$and let $x\_i'$ and $y\_i'$ be the images of $x\_i$ and $y\_i$ in $\mathbb R^{d'}$ such that all distances are preserved up to a relative (and hence absolute) error $\varepsilon$. Recall that the scalar product can be recovered from the distances by the formula
$$
 \langle y\_i-x\_i, x\_j-x\_i \rangle = \frac12(|x\_iy\_i|^2+|x\_ix\_j|^2-|y\_ix\_j|^2) .
$$
Since the distances are almost preserved and the product is nonnegative, for the images we get
$$
\langle y\_i'-x\_i', x\_j'-x\_i' \rangle \ge -3\varepsilon
$$
This means that all $x\_j'$ belong to the half-space $H\_i$ defined by
$$
 H\_i = \{ x'\in\mathbb R^{d'} : \langle x'-x\_i', y\_i'-x\_i' \rangle \ge -3\varepsilon \}
$$
Since $|y\_i'-x\_i'|=1\pm\varepsilon $, the point $x\_i'$ lies within distance $3\varepsilon/(1-\varepsilon)\le 4\varepsilon$ from the boundary of $H\_i$ (assuming $\varepsilon\le 0.1$). Therefore the projection of $X$ is contained in the convex set $K':=\bigcap\_i H\_i$ and lies within distance $4\varepsilon$ from its boundary.


