5
$\begingroup$

The Johnson-Lindenstrauss lemma states that by randomly projecting a set of $p$ points in $\mathbb{R}^n$ into $\mathbb{R}^k$ with $k$ at least some multiple of $\log p$, distances are approximately preserved with high probability. That is, random projections can reduce the dimension dramatically without losing information about the distances between points. Recently I've been looking at two papers by Dasgupta which seem to run against the intuition of Johnson-Lindenstrauss.

Dasgupta's result is that if a Gaussian in $\mathbb{R}^n$ with bounded eccentricity (condition number of the covariance) is randomly projected into $\mathbb{R}^k$ then as long as $k\log k$ is at most some fraction of $n$, the projection will be approximately a spherical Gaussian (its eccentricity will be close to $1$) with high probability. That seems to say that even relatively modest reductions in dimension lose most of the distance information in a set of points sampled i.i.d. from an eccentric Gaussian.

I'm not doubting the correctness of Johnson-Lindenstrauss or Dasgupta's results. On a formal level they don't really clash: the former relates $k$ to $p$ and the latter relates $k$ to $n$. Yet there still seems to be a tension here.

Soft question: How can I reconcile Johnson-Lindenstrauss and Dasgupta's results with my [lack of] intuition about high dimensional geometry?

In high dimensions, a set of points sampled i.i.d. from a Gaussian concentrates around an ellipsoid. One resolution could be that perhaps exponentially many (in the dimension) points are required to capture the geometry of the entire ellipsoid in some sense, so that Johnson-Lindenstrauss only applies to a very sparse sample of such an ellipsoid and loses most of the geometry of the ellipsoid itself. Or in other words that we should never think of a sub-exponentially-sized set of points as capturing the shape of a high-dimensional Gaussian or ellipsoid.

Slightly less soft question: Is this what is going on?

I'm not sure what tags are appropriate; feel free to add or change them.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Yes, one needs an exponential number of points to be able to metrically distinguish a high-dimensional ellipsoid from a high-dimensional ball, in order to overcome the concentration of measure effect that makes almost all distances between randomly selected points in an ellipsoid (or a Gaussian version thereof) concentrate around their mean. Assuming of course that the ellipsoid is not so eccentric to be nearly degenerate. $\endgroup$
    – Terry Tao
    Commented Sep 28, 2016 at 19:53
  • $\begingroup$ @TerryTao: Ok, so maybe part of my confusion stemmed from not looking closely at how the value of the eccentricity enters Dasgupta's assumptions. For the result to say something nontrivial the eccentricity needs to be $o(\sqrt{n})$. Given this it makes sense that concentration of measure applies. $\endgroup$
    – Noah Stein
    Commented Sep 28, 2016 at 20:11
  • 1
    $\begingroup$ Notice that this is close to being a dual version of the classical result from concentration of measure (a la Milman) that a random proportional dimensional cross section of a convex symmetric set that is of bounded distance from the Euclidean ball must be approximately the Euclidean ball of the cross section. $\endgroup$
    – Bill Johnson
    Commented Sep 29, 2016 at 0:51

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .