most recent 30 from http://mathoverflow.net 2013-05-22T05:58:21Z http://mathoverflow.net/feeds/user/26343 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106756/do-random-projections-approximately-preserve-convexity Cecil B 2012-09-09T21:27:43Z 2012-09-11T16:17:10Z

<p>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)$. </p> <p>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? </p>