Advanced Search

There exists an absolute constant $c_0$ such that for any n-dimensional Banach space E there exists a k-dimensional subspace F ⊂ E with k≤ n/2 such that $in{f}_{ellipsoid\epsilon \subset B_E}{(vol\left(B_E\right)/vol\left(\epsilon \right))}^{1/n}\le c_{0}in{f}_{zonoidZ\subset B_F}{(vol\left(B_F\right)/vol\left(Z\right))}^{1/k}$ . The concept of volume ratio with respect to ${\ell }_p$-spaces is used to prove the following distance estimate for $2\le q\le p<\infty$: $su{p}_{F\subset {\ell }_p,dimF=n}in{f}_{G\subset L_q,dimG=n}d(F,G){\sim }_{c_{pq}}{n}^{(q/2)(1/q-1/p)}$.

Let ε > 0 and 1 ≤ k ≤ n and let ${W_l}_{l=1}^p$ be affine subspaces of ℝⁿ, each of dimension at most k. Let $m=O\left({\epsilon }^{-2}(k+logp)\right)$ if ε < 1, and m = O(k + log p/log(1 + ε)) if ε ≥ 1. We prove that there is a linear map $H:ℝⁿ\to {ℝ}^m$ such that for all 1 ≤ l ≤ p and $x,y\in W_l$ we have ||x-y||₂ ≤ ||H(x)-H(y)||₂ ≤ (1+ε)||x-y||₂, i.e. the distance distortion is at most 1 + ε. The estimate on m is tight in terms of k and p whenever ε < 1, and is tight on ε,k,p whenever ε ≥ 1. We extend these results to embeddings into general normed spaces Y.

Algorithms are given for constructing a polytope P with n vertices (facets), contained in (or containing) a given convex body K in ${ℝ}^d$, so that the ratio of the volumes |K∖P|/|K| (or |P∖K|/|K|) is smaller than $f\left(d\right)/n^{2/(d-1)}$.