Dimension Reduction by Random Hyperplane Tessellations |
| |
Authors: | Yaniv Plan Roman Vershynin |
| |
Affiliation: | 1. Department of Mathematics, University of Michigan, 530 Church St., Ann Arbor, MI, 48109, USA
|
| |
Abstract: | 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∈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∈K to the sign vector with respect to the hyperplanes, we conclude that every bounded subset K of $mathbb{R}^{n}$ 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)?n, this yields a new discrete mechanism of dimension reduction for sets in Euclidean spaces. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|