text: 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.
  @cite_15: Abstract This paper contains two results concerning linear embeddings of subsets of Euclidean space in low-dimensional normed spaces. The first is an improvement of the known dependence on ɛ in Dvoretzky's theorem from order of ɛ 2 to order of ɛ (except for log factors). The second is a joint generalization of (Milman's version of) Dvoretzky's theorem and (a recent generalization by Klartag and Mendelson of) the Johnson–Lindenstrauss Lemma.
  @cite_14: 
  @cite_10: In this note, we establish some bounds on the supremum of certain empirical processes indexed by sets of functions with the same L2 norm. We present several geometric applications of this result, the most important of which is a sharpening of the Johnson–Lindenstrauss embedding Lemma. Our results apply to a large class of random matrices, as we only require that the matrix entries have a subgaussian tail.
summary: Embeddings of subsets @math into normed spaces were studied in geometric functional analysis @cite_10 @cite_14 . In particular, Klartag and Mendelson @cite_10 were concerned with embeddings into @math . They showed that for @math there exists a linear map @math such that @math One can choose @math to be an @math random matrix with Gaussian entries as in Theorem , or with sub-gaussian entries. Schechtman @cite_15 gave a simpler argument for a Gaussian matrix, which also works for embeddings into general normed spaces @math . In the specific case of @math , Schechtman's result states that for @math one has @math This result also follows from Lemma below.