Dimension Reduction by Random Hyperplane Tessellations

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,yaK 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 xaK to the sign vector with respect to the hyperplanes, we conclude that every bounded subset K of embeds into the Hamming cube {-1,1} (m) with a small distortion in the Gromov-Haussdorff metric. Since for many sets K one has m=m(K)a parts per thousand(a)n, this yields a new discrete mechanism of dimension reduction for sets in Euclidean spaces.