Dimension reduction by random hyperplane tessellations

Introduction

The main result of this paper is a bound on the minimal number $m=m(K,\delta)$ of hyperplanes that provide a uniform tessellation of a set $K$. It turns out that for a fixed accuracy $\delta$, an almost optimal estimate on $m$ depends only on one global parameter of $K$, namely the mean width. Recall that the Gaussian mean width of $K$ is defined as

Consider a subset $K\subseteq S^{n-1}$ and let $\delta>0$. Let

Theorem 1.2 has an equivalent formulation in the context of metric embeddings. It yields that every subset $K\subseteq S^{n-1}$ can be almost isometrically embedded into the Hamming cube $\{-1,1\}^{m}$ with $m=O(w(K)^{2})$.

To explain this statement, let us recall a few standard notions. An $\varepsilon$-isometry (or almost isometry) between metric spaces $(X,d_{X})$ and $(Y,d_{Y})$ is a map $f:X\to Y$ which satisfies

and such that for every $y\in Y$ one can find $x\in X$ satisfying $d_{Y}(y,f(x))\leq\varepsilon$. A map $f:X\to Y$ is an $\varepsilon$-isometric embedding of $X$ into $Y$ if the map $f:X\to f(X)$ is an $\varepsilon$-isometry between $(X,d_{X})$ and the subspace $(f(X),d_{Y})$. It is not hard to show that $X$ can be $2\varepsilon$-isometrically embedded into $Y$ (by means of a suitable map $f$) if $X$ has the Gromov-Haussdorff distance at most $\varepsilon$ from some subset of $Y$. Conversely, if there is an $\varepsilon$-isometry between $X$ and $f(X)$ then the Gromov-Haussdorff distance between $X$ and $f(X)$ is bounded by $\varepsilon$.

where $\operatorname*{sign}Ax$ denotes the vector of signs of the coordinates $\langle a_{i},x\rangle$ of $Ax$. The fraction $d_{A}(x,y)$ of the hyperplanes that separate points $x$ and $y$ thus equals

Then looking back at the definition of uniform tessellations, we observe the following fact:

Consider a $\delta$-uniform tessellation of a set $K\subseteq S^{n-1}$ by $m$ hyperplanes. Then the set $K$ (with the induced geodesic distance) can be $\delta$-isometrically embedded into the Hamming cube $\{-1,1\}^{m}$. The sign map provides such an embedding. ∎

This allows us to state Theorem 1.2 as follows:

Consider a subset $K\subseteq S^{n-1}$ and let $\delta>0$. Let

Then $K$ can be $\delta$-isometrically embedded into the Hamming cube $\{-1,1\}^{m}$.

Moreover, let $A$ be an $m\times n$ random matrix with independent $\mathcal{N}(0,1)$ entries. Then with probability at least $1-2\exp(-c\delta^{2}m)$, the sign map

2. Almost isometry of K𝐾K and the tessellation graph.

The image of the sign map $f$ in (1.3) has a special meaning. When the Hamming cube $\{-1,1\}^{m}$ is viewed as a graph (in which two points $u$, $v$ are connected if they differ in exactly one coordinate), the image of $f$ defines a subgraph of $\{-1,1\}^{m}$, which is called the tessellation graph of $K$. The tessellation graph has a vertex for each cell and an edge for each pair of adjacent cells, see Figure 2. Notice that the graph distance in the tessellation graph equals the number of hyperplanes that separate the two cells. Therefore the definition of a uniform tessellation yields:

Consider a $\delta$-uniform tessellation of a set $K\subseteq S^{n-1}$. Then $K$ is $\delta$-isometric to the tessellation graph of $K$. ∎

Hence we can read the conclusion of Theorem 1.2 as follows: $K$ is $\delta$-isometric to the graph of its tessellation by $m$ random hyperplanes, where $m\sim\delta^{-6}w(K)^{2}$.

3. Computing mean width

Powerful methods to estimate the mean width $w(K)$ have been developed in connection with stochastic processses. These methods include Sudakov’s and Dudley’s inequalities which relate $w(K)$ to the covering numbers of $K$ in the Euclidean metric, and the sharp technique of majorizing measures (see ).

Mean width has a simple (and known) geometric interpretation. By the rotational invariance of the Gaussian random vector $g$ in (1.2), one can replace $g$ with a random vector $\theta$ that is uniformly distributed on $S^{n-1}$, as follows:

Here $c_{n}$ are numbers that depend only on $n$ and such that $c_{n}\leq 1$ and $\lim_{n\to\infty}c_{n}=1$. We may refer to $\bar{w}(K)$ as the spherical mean width of $K$. Let us assume for simplicity that $K$ is symmetric with respect to the origin. Then $2\sup_{x\in K}|\langle\theta,x\rangle|$ is the width of $K$ in the direction $\theta$, which is the distance between the two supporting hyperplanes of $K$ whose normals are $\theta$. The spherical mean width $\bar{w}(K)$ is then twice the average width of $K$ over all directions.

4. Dimension reduction

Our results are already non-trivial in the particular case $K=S^{n-1}$. Since $w(S^{n-1})\leq\sqrt{n}$, Theorems 1.2 and 1.5 hold with $m\sim n$. But more importantly, many interesting sets $K\subset S^{n-1}$ satisfy $w(K)\ll\sqrt{n}$ and therefore make our results hold with $m\sim w(K)^{2}\ll n$. In such cases, one can view the sign map $f(x)=\operatorname*{sign}Ax$ in Theorem 1.5 as a dimension reduction mechanism that transforms an $n$-dimensional set $K$ into a subset of $\{-1,1\}^{m}$.

A heuristic reason why dimension reduction is possible is that the quantity $w(K)^{2}$ measures the effective dimension of a set $K\subseteq S^{n-1}$. The effective dimension $w(K)^{2}$ of a set $K\subseteq S^{n-1}$ is always bounded by the algebraic dimension, but it may be much smaller and it is robust with respect to perturbations of $K$. In this regard, the notion of effective dimension is parallel to the notion of effective rank of a matrix from numerical linear algebra (see e.g. ). With these observations in mind, it is not surprising that the “true”, effective dimension of $K$ would be revealed (and would be the only obstruction according to Theorem 1.5) when $K$ is being squeezed into a space of smaller dimension.

Let us illustrate dimension reduction on the example of finite sets $K\subset S^{n-1}$. Since $w(K)\leq C\sqrt{\log|K|}$ (see e.g. [16, (3.13)]), Theorem 1.5 holds with $m\sim\log|K|$, and we can state it as follows.

Let $K\subset S^{n-1}$ be a finite set. Let $\delta>0$ and $m\geq C\delta^{-6}\log|K|$. Then $K$ can be $\delta$-isometrically embedded into the Hamming cube $\{-1,1\}^{m}$. ∎

Like the Johnson-Lindenstrauss lemma, Corollary 1.7 can be proved directly by combining concentration inequalities for $d_{A}(x,y)$ with a union bound over $|K|^{2}$ pairs $(x,y)\in K\times K$. In fact, this method of proof allows for the weaker requirement $m\geq C\delta^{-2}\log|K|$. However, as we discuss later, this argument cannot be generalized in a straightforward way to prove Theorem 1.5 for general sets $K$. The Hamming distance $d_{A}(x,y)$ is highly discontinuous, which makes it difficult to extend estimates from points $x,y$ in an $\varepsilon$-net of $K$ to nearby points.

5. Cells of uniform tessellations

We mentioned two nice features of uniform tessellations in Facts 1.4 and 1.6. Let us observe one more property: all cells of a uniform tessellation have small diameter. Indeed, $d_{A}(x,y)=0$ iff points $x,y$ are in the same cell, so by (1.1) we have:

Every cell of a $\delta$-uniform tessellation has diameter at most $\delta$. ∎

With this, Theorem 1.2 immediately implies the following:

Consider a tessellation of a subset $K\subseteq S^{n-1}$ by $m\geq C\delta^{-6}w(K)^{2}$ random hyperplanes. Then, with probability at least $1-\exp(-c\delta^{2}m)$, all cells of the tessellation have diameter at most $\delta$.

This result has also a direct proof, which moreover gives a slightly better bound $m\sim\delta^{-4}w(K)^{2}$. We present this “curvature argument” in Section 3.

Here $d_{A}(x,y)$ denotes the fraction of the affine hyperplanes that separate $x$ and $y$.

7. Optimality

The main object of our study is $m(K)=m(K,\delta)$, the smallest number of hyperplanes that provide a $\delta$-uniform tessellation of a set $K\subseteq S^{n-1}$. One has

where $N(K,\delta)$ denotes the covering number of $K$, i.e. the smallest number of balls of radius $\delta$ that cover $K$. The upper bound in (1.5) is the conclusion of Theorem 1.2. The lower bound holds because a $\delta$-uniform tessellation provides a decomposition of $K$ into at most $2^{m}$ cells each of which lies in a ball of radius $\delta$ by Fact 1.8.

To compare the upper and lower bounds in (1.5), recall Sudakov’s inequality [16, Theorem 3.18] that yields

While Sudakov’s inequality cannot be reversed in general, there are many situations where it is sharp. Moreover, according to Dudley’s inequality (see [16, Theorem 11.17] and [18, Lemma 2.33]), Sudakov’s inequality can always be reversed for some scale $\delta>0$ and up to a logarithmic factor in $n$. (See also for a discussion of sharpness of Sudakov’s inequality.) So the two sides of (1.5) are often close to each other, but there is in general some gap. We conjecture that the optimal estimate is

so the mean width of $K$ seems to be completely responsible for the uniform tessellations of $K$.

Note that the lower bound in (1.5) holds in greater generality. Namely, it is not possible to have $m<\log_{2}N(K,\delta)$ for any decomposition of $K$ into $2^{m}$ pieces of diameter at most $\delta$. However, from the upper bound we see that with a slightly larger value $m\sim w(K)^{2}$, an almost best decomposition of $K$ is achieved by a random hyperplane tessellation.

In this paper we have not tried to optimize the dependence of $m(K,\delta)$ on $\delta$. This interesting problem is related to the open question on the optimal dependence on distortion in Dvoretzky’s theorem. We comment on this in Section 3.2.

8. Related work: embeddings of K𝐾K into normed spaces

This result also follows from Lemma 2.1 below.

9. Related work: one-bit compressed sensing

The problem of one-bit compressed sensing was introduced by Boufounos and Baraniuk . Jacques, Laska, Boufounos and Baraniuk realized a connection of this problem to uniform tessellations of the set of sparse signals $K=\{x\in S^{n-1}:\;|\operatorname*{supp}(x)|\leq s\}$, and to almost isometric embedding of $K$ into the Hamming cube $\{-1,1\}^{m}$. For this set $K$, they proved Corollary 1.9 with $m\sim\delta^{-1}s\log(n/\delta)$ and a version of Theorem 1.5 for $m\sim\delta^{-2}s\log(n/\delta)$. The authors of the present paper analyzed in a bigger set of “compressible” signals $K^{\prime}=\{x\in S^{n-1}:\;\|x\|_{1}\leq\sqrt{s}\}$ and proved for $K^{\prime}$ a version of Corollary 1.9 with $m\sim\delta^{-4}s\log(n/s)$. Since the mean widths of both sets $K$ and $K^{\prime}$ are of the order $\sqrt{s\log(n/s)}$, Theorem 1.5 holds for these sets with $m\sim\delta^{-6}s\log(n/s)$. In other words, apart from the dependence of $\delta$ (which is an interesting problem), the prior results follow as partial cases from Theorem 1.5.

It is important to note that Theorem 1.5 addresses only the theoretical aspect of one-bit compressed sensing problem, which guarantees that the quantized measurement map $f(x)=\operatorname*{sign}Ax$ well preserves the geometry of signals. But one also faces an algorithmic challenge – how to efficiently recover $x$ from $f(x)$, and specifically in polynomial time. We will not touch on this algorithmic aspect here but rather refer the reader to and to our forthcoming work which is based on the results of this paper.

10. Related work: locality-sensitive hashing

11. Overview of the argument

We instead attempt to prove Theorem 1.2 by an $\varepsilon$-net argument, which typically proceeds as follows: (a) show that $d_{A}(x,y)\approx d(x,y)$ holds for a fixed pair $x,y\in K$ with high probability; (b) take the union bound over all pairs $x,y$ in an finite $\varepsilon$-net $N_{\varepsilon}$ of $K$; (c) extend the estimate from $N_{\varepsilon}$ to $K$ by approximation. Unfortunately, as we indicate in Section 4 the approximation step (c) must fail due to the discontinuity of the Hamming distance $d_{A}(x,y)$.

A solution proposed in was to choose $\varepsilon$ so small that none of the random hyperplanes pass near points $x,y\in N_{\varepsilon}$ with high probability. This strategy was effective for the set $K=\{x\in S^{n-1}:\;|\operatorname*{supp}(x)|\leq s\}$ because the covering number of this specific set $K$ has a mild (logarithmic) dependence on $\varepsilon$, namely $\log N(K,\varepsilon)\leq s\log(Cn/\varepsilon s)$. However, adapting this strategy to general sets $K$ would cause our estimate on $m$ to increase by a factor of $n$.

12. Notation

(b) The following deviation inequality holds:

By the rotational invariance of the Gaussian distribution, $\frac{1}{m}\sum_{i=1}^{m}\varepsilon_{i}a_{i}$ is distributed identically with $g/\sqrt{m}$ where $g\sim\mathcal{N}(0,I_{n})$. Therefore

Thus $Z$ has Lipschitz constant bounded by $d(K)/\sqrt{m}$. We may now bound the deviation probability for $Z$ using the Gaussian concentration inequality (see [16, Equation 1.6]) as follows:

One can state Lemma 2.1 in terms of random matrices. Indeed, let $A$ be an $m\times n$ random matrix with independent $\mathcal{N}(0,1)$ entries. Then its rows $a_{i}$ satisfy the assumption of Lemma 2.1, and we can express $Z$ as

Let $A$ be the random matrix as in Remark 2.2. Using Lemma 2.1 for $K-K$ and noting the form of $Z$ in (2.3), we conclude that the following event holds with probability at least $1-2\exp(-m\delta^{2}/32)$:

The above argument shows in fact that Corollary 2.3 holds for

As we noticed in Remark 1.11, the quantity $w(K-K)$ more accurately reflects the geometric meaning of the mean width than $w(K)$.

Note that for the subspace $E=\ker A$ we have from (2.3) that $Z\geq\sup_{x\in K\cap E}\sqrt{\frac{2}{\pi}}\|x\|_{2}=\sqrt{\frac{2}{\pi}}\,d(K\cap E)$. Then Lemma 2.1 implies that

Proof of Corollary 1.9 by a curvature argument

In this section we give a short argument that leads to a version of Corollary 1.9 with a slightly better dependence of $m$ on $\delta$.

Consider a subset $K\subseteq S^{n-1}$ and let $\delta>0$. Let

The argument is based on Lemma 2.1. If points $x,y\in K$ belong to the same cell, then the midpoint $z=\frac{1}{2}(x+y)$ also belongs to the same cell (after normalization). Using Lemma 2.1 one can then show that $\|z\|_{2}\approx\frac{1}{2}(\|x\|_{2}+\|y\|_{2})=1$. Due to the curvature of the sphere, this forces the length of the interval $\|x-y\|_{2}$ to be small, which means that the diameter of the cell is small. The formal argument is below.

Assume that the event (3.1) holds. Consider a pair of points $x,y\in K$ that belong to the same cell of the tessellation, which means that

To complete the proof is suffices to show that $\|x-y\|_{2}\leq\delta$. This will give desired diameter $\delta$ in the Euclidean metric. Furthermore, since for small $\delta$ the Euclidean and the geodesic distances are equivalent, the conclusion will hold for the geodesic distance as well.

We shall use (3.1) for $x,y\in K$ and for the midpoint $z:=\frac{1}{2}(x+y)\in\frac{1}{2}(K+K)$. Clearly $\operatorname*{sign}\langle a_{i},z\rangle=\operatorname*{sign}\langle a_{i},x\rangle=\operatorname*{sign}\langle a_{i},y\rangle$, hence

By the parallelogram law, we conclude that

Unfortunately, the curvature argument does not lend itself to proving the more general result, Theorem 1.2 on uniform tessellations. To see why, suppose $x,y\in K$ do not belong to the same cell but instead $d_{A}(x,y)=d$ for some small $d\in(0,1)$. Consider the set of mismatched signs

These signs create an additional error term in the right hand side of (3.2), which is

By analogy with Lemma 2.1, we can expect that this term should be approximately equal $|T|/m=d$. If this is true, then (3.2) becomes in our situation $\|z\|_{2}\geq 1-2\varepsilon-d$, which leads as before to $\|x-y\|_{2}^{2}\lesssim\varepsilon+d$. Ignoring $\varepsilon$, we see that the best estimate the curvature argument can give is $d(x,y)\lesssim\sqrt{d_{A}(x,y)}$ rather than $d(x,y)\lesssim d_{A}(x,y)$ that is required in Theorem 1.2.

The weak point of this argument is that it takes into account the size of $T$ but ignores the nature of $T$. For every $i\in T$, the hyperplane $\{a_{i}\}^{\perp}$ passes through the arc connecting $x$ and $y$. If the length of the arc $d(x,y)$ is small, this creates a strong constraint on $a_{i}$. Conditioning the distribution of $a_{i}$ on the constraint that $i\in T$ creates a bias toward smaller values of $|\langle a_{i},x\rangle|$ and $|\langle a_{i},y\rangle|$. As a result, the conditional expected value of the error term (3.3) should be smaller than $d$. Computing this conditional expectation is not a problem for a given pair $x,y$, but it seems to be difficult to carry out a uniform argument over $x,y\in K$ where the (conditional) distribution of $a_{i}$ depends on $x,y$.

We instead propose a different and somewhat more conceptual way to deduce Theorem 1.2 from Lemma 2.1. This argument will be developed in the rest of this paper.

2. Dvoretzky theorem and dependence on δ𝛿\delta

The unusual dependence $\delta^{-4}$ in Theorem 3.1 is related to the open problem of the optimal dependence on distortion in the Dvoretzky theorem.

Toward Theorem 1.2: a soft Hamming distance

Our proof of Theorem 1.2 will be based on a covering argument. A standard covering argument of geometric functional analysis would proceed in our situation as follows:

Show that $d_{A}(x,y)\approx d(x,y)$ with high probability for a fixed pair $x,y$. This can be done using standard concentration inequalities.

Prove that $d_{A}(x,y)\approx d(x,y)$ uniformly for all $x,y$ in a finite $\varepsilon$-net $N_{\varepsilon}$ of $K$. Sudakov’s inequality can be used to estimate the cardinality of $N_{\varepsilon}$ via the mean width $w(K)$. The conclusion will follow from step 1 by the union bound over $(x,y)\in N_{\varepsilon}\times N_{\varepsilon}$.

Extend the estimate $d_{A}(x,y)\approx d(x,y)$ from $x,y\in N_{\varepsilon}$ to $x,y\in K$ by approximation.

Both positive and negative $t$ may be considered. For positive $t$ the soft Hamming distance counts the hyperplanes that separate $x,y$ well enough; for negative $t$ it counts the hyperplanes that separate or nearly separate $x,y$.

Clearly $d_{A}^{t}(x,y)$ is a non-increasing function of $t$. Moreover,

The soft Hamming distance for a fixed $t$ is as discontinuous as the usual (hard) Hamming distance. However, some version of continuity emerges when we allow $t$ to vary slightly:

Consider the events $\mathcal{F}_{i}=\mathcal{F}_{i}(x,y,t)$ from the definition of the soft Hamming distance (4.2). By the assumptions, we have $|\langle a_{i},x^{\prime}\rangle|\leq\varepsilon$, $|\langle a_{i},y^{\prime}\rangle|\leq\varepsilon$ for all $i\in[m]$. This implies by the triangle inequality that

We are ready to state a stronger version of Theorem 1.2 for the soft Hamming distance.

Consider a subset $K\subseteq S^{n-1}$ and let $\delta>0$. Let

Note that if we take $t=0$ in the above theorem, we recover Theorem 1.2. However, we find it easier to prove the result for general $t$, since in our argument we will work with different values of the $t$ for the soft Hamming distance.

Theorem 4.4 is proven in the next section.

Proof of Theorem 4.4 on the soft Hamming distance

We will follow the covering argument outlined in the beginning of Section 4, but instead of $d_{A}(x,y)$ we shall work with the soft Hamming distance $d_{A}^{t}(x,y)$.

The first inequality follows from (5.1) and Jensen’s inequality. To prove the second inequality, we use the events $\mathcal{E}_{i}$ and $\mathcal{F}_{i}$ from Equations (4.1), (4.2) defining the hard and soft Hamming distances, respectively. It follows that

Now we upgrade Lemma 5.1 to an concentration inequality:

A standard Chernoff bound for binomial random variables states that

see e.g. [7, Corollary A.1.7]. The triangle inequality completes the proof. ∎

2. Concentration of distance over an ε𝜀\varepsilon-net

Let us fix a small $\varepsilon>0$ whose value will be determined later. Let $N_{\varepsilon}$ be an $\varepsilon$-net of $K$ in the Euclidean metric. By Sudakov’s inequality (see [16, Theorem 3.18]), we can arrange the cardinality of $N_{\varepsilon}$ to satisfy

We can decompose every vector $x\in K$ into a center $x_{0}$ and a tail $x^{\prime}$ so that

We first control the centers by taking a union bound in Lemma 5.2 over the net $N_{\varepsilon}$:

Let $A$ a random Gaussian matrix be as in Theorem 4.4. Let $N_{\varepsilon}$ be a subset of $S^{n-1}$ whose cardinality satisfies (5.2). Let $\delta>0$, and assume that

By Lemma 5.3 and a union bound over the set of pairs $(x_{0},y_{0})\in N_{\varepsilon}\times N_{\varepsilon}$, we obtain

where the last inequality follows by (5.2) and (5.4). The proof is complete. ∎

3. Control of the tails

Now we control the tails $x^{\prime}\in(K-K)\cap\varepsilon B_{2}^{n}$ in decomposition (5.3).

Consider a subset $K\subseteq S^{n-1}$ and let $\varepsilon>0$. Let

Consider independent random vectors $a_{1},\ldots,a_{m}\sim\mathcal{N}(0,I_{n})$. Then with probability at least $1-2\exp(-cm)$, one has

Let us apply Lemma 2.1 for the set $T=(K-K)\cap\varepsilon B_{2}^{n}$ instead of $K$, and for $u=\varepsilon/8$. Since $d(K)=\max_{x^{\prime}\in T}\|x^{\prime}\|_{2}\leq\varepsilon$, we obtain that the following holds with probability at least $1-2\exp(-cm)$:

Note that $w(T)\leq w(K-K)\leq 2w(K)$. So using the assumption on $m$ we conclude that the quantity in (5.5) is bounded by $\varepsilon$, as claimed. ∎

4. Approximation

Now we establish a way to transfer the distance estimates from an $\varepsilon$-net $N_{\varepsilon}$ to the full set $K$. This is possible by a continuity property of the soft Hamming distance, which we outlined in Lemma 4.3. This result requires the perturbation to be bounded in $L_{\infty}$ norm. However, in our situation the perturbations are going to be bounded only in $L_{1}$ norm due to Lemma 5.4. So we shall prove the following relaxed version of continuity:

Consider the events $\mathcal{F}_{i}=\mathcal{F}_{i}(x,y,t)$ from the definition of the soft Hamming distance (4.2). By the assumptions, we have

This proves the first inequality in (5.6). The proof of the second inequality is similar. ∎

5. Proof of Theorem 4.4.

Now we are ready to combine all the pieces and prove Theorem 4.4. To this end, consider the set $K$, numbers $\delta$, $m$, $t$, and the random matrix $A$ as in the theorem. Choose $\varepsilon=\delta^{2}/100$ and $M=10/\delta$.

Consider an $\varepsilon$-net $N_{\varepsilon}$ of $K$ as we described in the beginning of Section 5.2. Let us apply Lemma 5.3 that controls the distances on $N_{\varepsilon}$ along with Lemma 5.4 that controls the tails. By the assumption on $m$ in the theorem and by our choice of $\varepsilon$, both requirements on $m$ in these lemmas hold. By a union bound, with probability at least $1-4\exp(-c\delta^{2}m)$ the following event holds: for every $x_{0},y_{0}\in N_{\varepsilon}$ and $x^{\prime},y^{\prime}\in(K-K)\cap\varepsilon B_{2}^{n}$, one has

Let $x,y\in K$. As we described in (5.3), we can decompose the vectors as

The bounds in (5.8) guarantee that the continuity property (5.6) in Lemma 5.5 holds. This gives

Finally, by the choice of $\varepsilon$ and $M$ we obtain

This completes the proof of Theorem 4.4. ∎

Fix a large number $t\geq 2$ whose value will be chosen later and consider the set

where the last inequality holds because $w(K)\geq\sqrt{2/\pi}\sup_{x\in K}\|x\|_{2}\geq 1/\sqrt{2\pi}$ by (6.1).

Consider arbitrary vectors $x$ and $y$ in $K$ and the corresponding vectors $x^{\prime}=Q(x\oplus t)$ and $y^{\prime}=Q(x\oplus t)$ in $K^{\prime}$. Let us relate the distances between $x^{\prime}$ and $y^{\prime}$ appearing in (6.3) to corresponding distances between $x$ and $y$.

Next we analyze the normalized geodesic distance $d(x^{\prime},y^{\prime})$, which satisfies

Denoting $t_{x}=\|x\oplus t\|_{2}$ and $t_{y}=\|y\oplus t\|_{2}$ and using the triangle inequality, we obtain

Note that (6.1) yields that $t\leq t_{x},t_{y}\leq\sqrt{t^{2}+1}$. It follows that $|t_{x}^{-1}-t^{-1}|\leq 0.5t^{-3}$ and the same bound holds for the other two similar terms in (6.6). Using this and (6.1) we conclude that $\varepsilon\leq t^{-2}$. Putting this into (6.5) and using the triangle inequality twice, we obtain

Finally, we use this bound and (6.4) in (6.3), which gets us

Now we can assign the values $t:=2C_{1}/\delta$ and $\delta_{0}=\delta^{2}/(4\pi C_{1})$ so the right hand side of (6.7) is bounded by $\delta$, as required. Note that the condition $m\geq C\delta_{0}^{-6}w(K)^{2}$ that we used above in order to apply Theorem 1.2 is satisfied by (6.2). This completes the proof of Theorem 1.10. ∎

References