Dimension reduction by random hyperplane tessellations

Details Dimension reduction by random hyperplane tessellations Dimension reduction by random hyperplane tessellations

2011-11-18

arxiv.org/abs/1111.4452v1

Mathematics

Probability

17 pages, 3 figures

Scientific paper

Given a subset K of the unit Euclidean sphere, we estimate the minimal number m = m(K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x, y in K is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m = O(w(K)^2) where w(K) is the Gaussian mean width of K. Using the map that sends x in K to the sign vector with respect to the hyperplanes, we conclude that every bounded subset K of R^n embeds into the Hamming cube {-1, 1}^m with a small distortion in the Gromov-Haussdorf metric. Since for many sets K one has m = m(K) << n, this yields a new discrete mechanism of dimension reduction for sets in Euclidean spaces.

Affiliated with

Also associated with

No associations

Rating

Dimension reduction by random hyperplane tessellations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dimension reduction by random hyperplane tessellations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dimension reduction by random hyperplane tessellations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-550030