25
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ Are you asking whether a) there exists a single such projection, b) with very high probability there exists a single such projection, or c) a randomly chosen projection satisfies your criterion with very high probability? $\endgroup$
    – JSE
    Sep 10, 2012 at 15:16

4 Answers 4

17
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ So there is a big difference between Euclidean closeness and closeness as measured by the convex body. Interesting. $\endgroup$ Sep 10, 2012 at 17:51
9
$\begingroup$

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:

In

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).

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ By J-L, you cannot get a counterexample using points on an ellipsoid. $\endgroup$ Sep 10, 2012 at 13:21
  • 1
    $\begingroup$ Could you elaborate? $\endgroup$
    – Igor Rivin
    Sep 10, 2012 at 13:29
  • $\begingroup$ J-L says that you can approximately preserve the Euclidean norm of vectors with a random orthogonal projection of the right rank, so if your points have Euclidean norm one, the images have approximately the same Euclidean norm and hence are close to the boundary of a symmetric convex set. This is what the OP was saying up front. The OP wants a similar statement when the points are on the surface of a general convex body. This cannot be done with any operator of rank like what appears in J-L (rank logarithmic in the number $k$ of points) but there are positive results for rank $k6\alpha$ .... $\endgroup$ Sep 10, 2012 at 14:18
  • $\begingroup$ ... rank $k^a$ for arbitrary $a>0$. I'll write an answer when I have time unless I am lucky enough that someone does it before me. $\endgroup$ Sep 10, 2012 at 14:47
  • $\begingroup$ I am awaiting @Bill's answer with bated breath, but just to clarify: are you saying that the problem with my idea is that rank 1 is too small for J-L (and its friends) to work? $\endgroup$
    – Igor Rivin
    Sep 10, 2012 at 15:44
6
$\begingroup$

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.


              Ellipsoid

$\endgroup$
2
  • 2
    $\begingroup$ The problem with this is that $3$ is not very big compared to $2,$ and the OP is asking for an asymptotic result. However, another thought in my answer.. $\endgroup$
    – Igor Rivin
    Sep 10, 2012 at 1:24
  • 2
    $\begingroup$ By J-L, you cannot get a counterexample using points on an ellipsoid. $\endgroup$ Sep 10, 2012 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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