Do random projections (approximately) preserve convexity? - MathOverflow

Do random projections (approximately) preserve convexity?

2012-09-09T21:27:43Z

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?

Answer by Joseph O'Rourke for Do random projections (approximately) preserve convexity?

2012-09-10T01:03:20Z

Not an answer, just a thought.

It seems a bit too much to hope for. Here are 300 points randomly sprinkled on the surface of an ellipsoid in $\mathbb{R}^3$, and then projected to two dimensions. No matter how the projection plane is oriented, the projected points are not near the boundary of a two-dimensional convex set, but rather fill in the interior of such a set.

Answer by Igor Rivin for Do random projections (approximately) preserve convexity?

2012-09-10T01:28:38Z

Notice that the projection of a high-dimensional sphere onto one dimension looks gaussian (a fact first observed by Boltzmann, as far as I know). So, if you have a set of points equidistributed on the $\mathbb{S}^n,$ their projection onto one dimension will be gaussian on the interval, so will exhibit the opposite of the behavior you conjecture (notice that this will be for any projection onto one dimension). Since, as @Joseph points out in his answer, there is not much difference between different small dimensions, I would be quite confident that the answer to your question is NO.

Answer by Sergei Ivanov for Do random projections (approximately) preserve convexity?

2012-09-10T16:09:37Z

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.

Answer by Bill Johnson for Do random projections (approximately) preserve convexity?

2012-09-10T17:35:24Z

Negative result:

See p. 377 in Chapter 15 of Matousek's book, which can be found here. In short, if you want the image of the $k$ points to be between the surface of a convex body $K$ and the surface of $DK$ for some $D>1$, you need the operator to have rank at least $k^{f(D)}$ for some function $f$.

Positive result on a related problem:

Johnson, William B.; Lindenstrauss, Joram; Schechtman, Gideon On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. Geometrical aspects of functional analysis (1985/86), 177–184, Lecture Notes in Math., 1267, Springer, Berlin, 1987,

it is proved that for some constant $C$, if you have $k$ points on the surface of a symmetric convex body, then you can put the points isometrically into a suitable $\ell_\infty^m$ in such a way that a random projection of order rank $k^{1/D}$ will place the points between the surface of a symmetric convex body $K$ and the surface of $CDK$; see the paper for a precise statement. I don't think symmetry places much of a role here. We were interested in the embedding of points into a Banach space and so did not think about general convex bodies. The embedding theorem we proved was later made obsolete by Matousek when he proved that and metric space with size $k$ embeds into $\ell_\infty^{n}$ with distortion $D$ with $n$ about $Dk^{1/(2D)} \log k$ (see p. 404 at the above given link).