On Fast Johnson–Lindenstrauss Embeddings of Compact Submanifolds of $\mathbbm {R}^N$ with Boundary

Abstract

Let ${\mathcal {M}}$ be a smooth d-dimensional submanifold of $\mathbbm {R}^N$ with boundary that’s equipped with the Euclidean (chordal) metric, and choose $m \le N$. In this paper we consider the probability that a random matrix $A\in {\mathbbm {R}}^{m\times N}$ will serve as a bi-Lipschitz function $A:{\mathcal {M}} \rightarrow \mathbbm {R}^m$ with bi-Lipschitz constants close to one for three different types of distributions on the $m\times N$ matrices A, including two whose realizations are guaranteed to have fast matrix-vector multiplies. In doing so we generalize prior randomized metric space embedding results of this type for submanifolds of $\mathbbm {R}^N$ by allowing for the presence of boundary while also retaining, and in some cases improving, prior lower bounds on the achievable embedding dimensions m for which one can expect small distortion with high probability. In particular, motivated by recent modewise embedding constructions for tensor data, herein we present a new class of highly structured distributions on matrices which outperform prior structured matrix distributions for embedding sufficiently low-dimensional submanifolds of $\mathbbm {R}^N$ (with $d\lesssim \sqrt{N}$) with respect to both achievable embedding dimension, and computationally efficient realizations. As a consequence we are able to present, for example, a general new class of Johnson–Lindenstrauss embedding matrices for ${\mathcal {O}}(\log ^c N)$-dimensional submanifolds of $\mathbbm {R}^N$ which enjoy ${\mathcal {O}}(N \log (\log N))$-time matrix vector multiplications.

Appendix A: The Proof of Theorem 3.4

The following lemma describes properties that the matrices A and B can have in order to guarantee that E in (1) will approximately preserve the norms of all elements of an arbitrary bounded set $S \subset \mathbbm {R}^N$. Though we will present the proof in general, we will be primarily interested in the case where S contains all unit norm s-sparse vectors so that

$$\begin{aligned} S = U\left( \bigcup _{\begin{array}{c} S' \subset [N]\\ |S'| = s \end{array}}{\text {span}}{ \bigl (\{ \textbf{e}_j\}_{j \in S'} \bigr )} \right) . \end{aligned}$$

(41)

Lemma A.1

Let $\epsilon \in (0,{1}/{3})$, $S \subset \mathbbm {R}^N$, and $A \in \mathbbm {R}^{m_1 \times m_1^2}$, $B \in \mathbbm {R}^{m_2 \times N/m_1}$, $C \in \mathbbm {R}^{N/m_1 \times N}$, and $E \in \mathbbm {R}^{m_2 \times N}$ be as above in (1) with $m_1 \ge m_2$. Furthermore, let $a_E := \max {\bigl \{ \sup \nolimits _{\textbf{x} \in U(S - S)} \Vert E \textbf{x} \Vert _2,1 \bigr \}}$, ${{\mathcal {C}}}_{\delta } \subset S$ be a finite $\delta$-cover of S for $\delta \le \epsilon /a_E$, and suppose that

• (a) A is an $\epsilon$-JL map of $P_j {{\mathcal {C}}}_{\delta }$ into $\mathbbm {R}^{m_1}$ for all $j \in [N/m_1^2]_0$, and that

• (b) $B/{\sqrt{m_2}}$ is an $\epsilon$-JL map of $C {{\mathcal {C}}}_{\delta }$ into $\mathbbm {R}^{m_2}$.

Then,

$$\begin{aligned} (1 - 2\epsilon ) \Vert \textbf{x} \Vert _2 - \epsilon \left( 1+\sqrt{\frac{5}{3}}\,\right) \le \Vert E \textbf{x} \Vert _2 \le \biggl (1 + \frac{3\epsilon }{2}\biggr ) \Vert \textbf{x} \Vert _2 + \epsilon (1+\sqrt{2}) \end{aligned}$$

(42)

will hold for all $\textbf{x} \in S$. If, in addition, S is a subset of the unit sphere such that $\Vert \textbf{x} \Vert _2 = 1$ for all $\textbf{x} \in S$, then $E = BC/{\sqrt{m_2}} \in \mathbbm {R}^{m_2 \times N}$ will also be a $14 \epsilon$-JL map of S into $\mathbbm {R}^{m_2}$.

Proof

By Lemma 3.1 we see that E will be a $3\epsilon$-JL map of ${{\mathcal {C}}}_{\delta }$ into $\mathbbm {R}^{m_2}$ since

$$\begin{aligned} \begin{aligned} (1-2\epsilon ) \Vert \textbf{x} \Vert _2^2&\le (1-\epsilon )^2 \Vert \textbf{x} \Vert _2^2 \le (1-\epsilon ) \Vert C \textbf{x} \Vert _2^2\le \Vert E \textbf{x}\Vert ^2_2\\&\le (1+\epsilon ) \Vert C \textbf{x} \Vert _2^2 \le (1+\epsilon )^2 \Vert \textbf{x} \Vert _2^2 \le (1 + 3 \epsilon ) \Vert \textbf{x} \Vert _2^2 \end{aligned} \end{aligned}$$

(43)

will hold for all $\textbf{x} \in {{\mathcal {C}}}_{\delta }$. Continuing, let $\textbf{y} \in S$ and choose $\textbf{x} \in {{\mathcal {C}}}_{\delta } \subset S$ be such that $\Vert \textbf{y} - \textbf{x} \Vert _2 \le \delta$. Using (43) we have that

$$\begin{aligned} \Vert E \textbf{y} \Vert _2{} & {} \le \Vert E\textbf{x} \Vert _2 + \Vert E(\textbf{y} - \textbf{x}) \Vert _2 \le \sqrt{1 + 3\epsilon } \,\Vert \textbf{x} \Vert _2 + a_E \Vert \textbf{y} - \textbf{x} \Vert _2 \\{} & {} \le \sqrt{1 + 3\epsilon } \,\Vert \textbf{y} \Vert _2 + \delta \sqrt{1 + 3\epsilon } + a_E \delta \le \biggl (1 + \frac{3\epsilon }{2}\biggr )\Vert \textbf{y} \Vert _2 + \epsilon (1+\sqrt{2}).\nonumber \end{aligned}$$

(44)

Similarly, we will also have that

$$\begin{aligned} \Vert E \textbf{y} \Vert _2\ge & {} \Vert E\textbf{x} \Vert _2 - \Vert E(\textbf{y} - \textbf{x}) \Vert _2 \ge \sqrt{1 - 2\epsilon } \,\Vert \textbf{x} \Vert _2 - a_E \Vert \textbf{y} - \textbf{x} \Vert _2\\\ge & {} \sqrt{1 - 2\epsilon }\,\Vert \textbf{y} \Vert _2 - \delta \sqrt{1 + 2\epsilon } - a_E \delta \ge (1 - 2\epsilon ) \Vert \textbf{y} \Vert _2 - \epsilon \left( 1+\sqrt{\frac{5}{3}}\,\right) .\nonumber \end{aligned}$$

(45)

Combining (44) and (45) gives us (42). Finally, if all the elements of S are unit norm, then we can see from (44) and (45) that

$$\begin{aligned} (1-5 \epsilon ) \Vert \textbf{y} \Vert _2 \le \Vert E \textbf{y} \Vert _2 \le (1+4 \epsilon ) \Vert \textbf{y} \Vert _2 \end{aligned}$$

will hold for all $\textbf{y} \in S$. Squaring throughout now proves the remaining claim. $\square$

Note that Lemma A.1 requires the matrix $B/\sqrt{m_2}$ to be an $\epsilon$-JL map of a finite subset $S_C$ of C(S) (see assumption (b)). In addition, we need to have some way of bounding $a_E = \sup \nolimits _{\textbf{x} \in U(S - S)} \Vert E \textbf{x} \Vert _2$ from above in order to safely upper bound the cardinality of $S_C = C(C_\delta )$ in the first place. The next lemma addresses both of these needs for sub-Gaussian matrices B.

Lemma A.2

Let $\epsilon , p \in (0, {1}/{3})$, $S \subset \mathbbm {R}^N$, and $S_C \subset C(S) \subset \mathbbm {R}^{N/m_1}$ be finite. Furthermore, suppose that $B \in \mathbbm {R}^{m_2 \times N/m_1}$ in the definition of E in (1) has $m_2 \ge c_1 \epsilon ^{-2} \ln (|S_C|/p)$ independent, isotropic, and sub-Gaussian rows. Then, both

• (i) $B/{\sqrt{m_2}}$ will be an $\epsilon$-JL map of $S_C$ into $\mathbbm {R}^{m_2}$, and

• (ii)
  $$\begin{aligned} \sup _{\textbf{x} \in U(S- S)} \Vert E \textbf{x} \Vert _2\le & {} c_2\Vert A\Vert \left( \frac{w(U(S-S)) + \sqrt{\ln ({1}/{p})}}{\sqrt{m_2}}+1\right) \\\le & {} c_3 \biggl (\frac{\Vert A\Vert }{\sqrt{m_2}} \biggr )\left( \sqrt{N} + \sqrt{\ln \frac{1}{p}}\,\right) \end{aligned}$$

will hold simultaneously with probability at least $1-p$. Here $c_1, c_2, c_3 \in \mathbbm {R}^+$ are constants that only depend on the distributions of the rows of B (i.e., they are absolute constants once distributions for the rows of B are fixed).

Proof

To prove that both conclusions (i) and (ii) above hold simultaneously with probability at least $1-p$, we will prove that each one holds separately with probability at least $1 - p/2$. The desired result will then follow from the union bound.

To establish conclusion (i) with probability at least $1-p/2$ one may simply appeal, e.g., to the proof of [24, Lem. 9.35]. Toward establishing conclusion (ii) we first note that

(46)

Continuing, we have

$$\begin{aligned} \sup _{\textbf{x} \in U(S - S)} \Vert E \textbf{x} \Vert _2&= \frac{1}{\sqrt{m_2}} \sup _{\textbf{x} \in C(U(S - S))} \Vert B \textbf{x} \Vert _2\\&\le \frac{1}{\sqrt{m_2}} \sup _{\textbf{x} \in C(U(S - S))} \bigl | \Vert B \textbf{x} \Vert _2 - \sqrt{m_2} \Vert \textbf{x} \Vert _2 \bigr | + \sqrt{m_2}\, \Vert \textbf{x} \Vert _2\\&\le \frac{1}{\sqrt{m_2}} \sup _{\textbf{x} \in C(U(S - S))} \bigl | \Vert B \textbf{x} \Vert _2 - \sqrt{m_2}\Vert \textbf{x} \Vert _2 \bigr | + \sup _{\textbf{x} \in U(S - S)} \Vert C \textbf{x} \Vert _2. \end{aligned}$$

Now appealing to Theorem 2.1 and (46) we can see that

$$\begin{aligned} \sup _{\textbf{x} \in U(S - S)} \Vert E \textbf{x} \Vert _2&\le \frac{{\tilde{c}}\bigl ( w(C(U(S-S))) + \sqrt{\ln ({4}/{p})}\,\sup _{\textbf{x} \in C(U(S-S))} \Vert \textbf{x} \Vert _2 \bigr )}{\sqrt{m_2}} + \Vert C\Vert \\&\le \frac{{\tilde{c}} \bigl ( w(C(U(S-S))) + \sqrt{\ln ({4}/{p})} \cdot \Vert A\Vert \bigr )}{\sqrt{m_2}} + \Vert A\Vert \end{aligned}$$

will hold with probability at least $1 - p/2$, where ${\tilde{c}} \in \mathbbm {R}^+$ is a constant that only depends on the distributions of the rows of B. Finally, using properties of Gaussian width (see, e.g., [46, Exer. 7.5.4]) the last inequality can be simplified further to

Using (46) one last time and simplifying using that $\ln (1/p) \ge 1$ now yields the first inequality in (ii) above.

To obtain a different version of the second inequality in (ii) one might be tempted to use, e.g., [46, Thm. 4.4.5] and then repeat analogous simplifications to those just performed above. Indeed, doing so provides a slight better bound on $\sup \nolimits _{\textbf{x} \in U(S - S)} \Vert E \textbf{x} \Vert _2$ than the second inequality in (ii) does in the end. However, for our purposes the second inequality in (ii) suffices and also follows automatically from what we have already proven given that $w(U(S-S)) \le w (U(\mathbbm {R}^N)) \le \sqrt{N} + c''$ for an absolute constant $c''$ (see, e.g., [46, Ex. 7.5.7]). Simplifying using that $N / m_2 \ge 1$ finishes the job. $\square$

Lemma A.2 proposes that the matrix B in the definition of E in (1) be chosen as a sub-Gaussian random matrix. Indeed, it demonstrates that doing so will at least partially fulfill the requirements of Lemma A.1 with high probability. Our next lemma proposes an auspicious choice for the remaining matrix $A \in \mathbbm {R}^{m_1 \times m_1^2}$.

Lemma A.3

Fix $p,\epsilon \in (0,1/3)$, a finite set ${\tilde{S}} \subset \mathbbm {R}^N$, $K \in [1,N^{{1}/{4}})$, and suppose that $m_1 \in \mathbbm {Z}^+$ satisfies

$$\begin{aligned} \sqrt{N}\ge m_1\ge \frac{c K^2}{\epsilon ^2} \ln \frac{N |{\tilde{S}}|}{p} \ln \frac{N}{p}\ln ^2\frac{\ln ( N |{\tilde{S}}| / p) K^2}{\epsilon }, \end{aligned}$$

where $c \in \mathbbm {R}^+$ is an absolute constant. Next, let $U \in \mathbbm {R}^{m_1^2 \times m_1^2}$ be a unitary matrix with BOS constant $m_1\max \nolimits _{k,t}|u_{t,k}|\le K$, $D\in \{0,-1,1\}^{m_1^2\times m_1^2}$ is a diagonal matrix with i.i.d. $\pm 1$ Rademacher random variables on its diagonal, and $R \in \{ 0,1 \}^{m_1 \times m_1^2}$ is $m_1$ rows independently selected uniformly at random from the $m_1^2 \times m_1^2$ identity matrix; Set $A := \sqrt{m_1}\, R U D$. Then, $\Vert A \Vert \le m_1$ always. Furthermore, A will be an $\epsilon$-JL map of $P_j {\tilde{S}}$ into $\mathbbm {R}^{m_1}$ for all $j \in [N/m_1^2]_0$ with probability at least $1 - p$.

Proof

Due to the unitary nature of both U and all admissible D we have

where $\Vert R \Vert _1 := \max \limits _{1 \le j \le m_1^2} \sum \nolimits _{\ell = 1}^{m_1} |R_{\ell ,j}| \le m_1$ for all admissible R. This proves the claim regarding $\Vert A \Vert$.

Now fix $j \in [N/m_1^2]_0$ and let

$$\begin{aligned}{} & {} s := 16 \ln \frac{ 8 e N |{\tilde{S}}|}{p} \ge \mathop {\max \limits _{j \in [N/m_1^2]_0}} 16 \ln \frac{8 N|P_j{\tilde{S}}|}{m_1^2 p}. \end{aligned}$$

For this choice of s [24, Thm. 9.36] guarantees that A will be an $\epsilon$-JL map of $P_j {\tilde{S}}$ into $\mathbbm {R}^{m_1}$ with probability at least $1 - p/(2N/m_1^2)$ provided that $\sqrt{m_1}\,RU$ has the RIP of order $(2s,\epsilon /4)$. The union bound then guarantees that A will be an $\epsilon$-JL map of $P_j {\tilde{S}}$ into $\mathbbm {R}^{m_1}$ for all $j \in [N/m_1^2]_0$ with probability at least $1-p/2$. To finish, by a final application of the union bound it suffices to prove that $\sqrt{m_1}\,RU$ will indeed have the RIP of order $(2s,\epsilon /4)$ with probability at least $1-p/2$. This RIP condition is provided by Corollary 2.4 for any BOS matrix $({m_1}/{\sqrt{m'}}) R'U \in \mathbbm {C}^{m' \times m_1^2}$ with at least

$$\begin{aligned} m' \ge m_{\min } := \left\lceil \frac{c K^2}{\epsilon ^2} \ln \frac{N|{\tilde{S}}|}{p}\ln \frac{m_1}{p}\ln ^2\frac{\ln (N|{\tilde{S}}|/p) K^2}{\epsilon }\right\rceil \end{aligned}$$

rows, where $c \in \mathbbm {R}^+$ is a sufficiently large absolute constant. Note that our assumed bounds on $m_1$ guarantee that $m_1 \ge m_{\min }$. Furthermore, if $m_1 > m_{\min }$ we can simply increase $m'$ to $m_1$ without losing the desired RIP condition. $\square$

We are now prepared to prove the main result of this section.

Theorem A.1

Let $S \subset U(\mathbbm {R}^N)$, $K \in [1,N^{1/4})$, $\epsilon \in (0,1/3)$, $p \in (e^{-N},1/3)$, and fix a sequence $X = X_1,\dots$ of i.i.d. mean zero, sub-Gaussian random variables from which to draw the entries of B in (1). Next, suppose that $m_1 \in \mathbbm {Z}^+$ satisfies

$$\begin{aligned} \sqrt{N}\ge m_1\ge \frac{c_2 K^2}{\epsilon ^2}\ln \frac{N{\mathcal {N}}(S,{\epsilon }/{c_1 N})}{p}\ln \frac{N}{p}\ln ^2\biggl (\frac{ K^2}{\epsilon }\ln \frac{N {\mathcal {N}}(S,{\epsilon }/{c_1 N})}{p}\biggr ), \end{aligned}$$

and that $m_2 \in \mathbbm {Z}^+$ satisfies

$$\begin{aligned} m_1 \ge m_2 \ge c_3 \epsilon ^{-2} \ln \frac{{\mathcal {N}}(S, \delta )}{p} \end{aligned}$$

for $\delta := c_4 \epsilon /(m_1( w(U(S-S)) + \sqrt{\ln (1/p)}))$, where $c_1, c_2, c_3, c_4 \in \mathbbm {R}^+$ are absolute constants. Finally, choose $A \in \mathbbm {R}^{m_1 \times m_1^2}$ and $B \in \mathbbm {R}^{m_2 \times N/m_1}$ in (1) such that:

• (i) $A := \sqrt{m_1}\,R U D$ where $U \in \mathbbm {R}^{m_1^2 \times m_1^2}$ is a unitary matrix with BOS constant $m_1\max \nolimits _{k,t}|u_{t,k}| \le K$, $D \in \{ 0, -1, 1 \}^{m_1^2 \times m_1^2}$ is a diagonal matrix with i.i.d. $\pm 1$ Rademacher random variables on its diagonal, and $R \in \{ 0,1 \}^{m_1 \times m_1^2}$ is $m_1$ rows independently selected uniformly at random from the $m_1^2 \times m_1^2$ identity matrix;

• (ii) B has i.i.d. mean zero, sub-Gaussian entries drawn according to the first $m_2 N / m_1$ random variables in X.

Then, $E =BC/{\sqrt{m_2}} \in \mathbbm {R}^{m_2 \times N}$ will be an $\epsilon$-JL map of S into $\mathbbm {R}^m_2$ with probability at least $1-p$. Furthermore, if $A \in \mathbbm {R}^{m_1 \times m_1^2}$ has an $m_1^2f(m_1)$-time matrix-vector multiplication algorithm, then E will have an ${\mathcal {O}}(Nf(m_1))$-time matrix-vector multiply.

Proof

Note the stated result follows from Lemma A.1 provided that its assumptions (a) and (b) both hold with $\epsilon \leftarrow \epsilon /14$ and $\delta$ sufficiently small. Hence, we seek to establish that both of these assumptions will simultaneously hold with probability at least $1-p$ for our choices of A and B above. We will use Lemmas A.2 and A.3 to accomplish this objective below, thereby proving the theorem.

To begin, we will apply Lemma A.2 with $S \leftarrow S$, $p \leftarrow p/3$, $\epsilon \leftarrow \epsilon / 14$, and $S_C \leftarrow C{\mathcal {C}}_{\delta }$ where ${\mathcal {C}}_\delta \subset S$ is a minimal $\delta$-cover of S. In doing so we note that $c_1, c_2, c_3$ in Lemma A.2 will be absolute constants given X.⁷ As a consequence we learn that both the event

$$\begin{aligned} {\mathcal {E}}_{(c)} := \biggl \{\frac{1}{\sqrt{m_2}} B\ \text {is an } \frac{\epsilon }{14}\text {-JL map of }C {\mathcal {C}}_{\delta }\text { into } \mathbbm {R}^{m_2} \biggr \}, \end{aligned}$$

and

$$\begin{aligned} \begin{aligned} a_E&\le \sup _{\textbf{x} \in U(S - S)} \Vert E \textbf{x} \Vert _2+1 \le cm_1\left( \frac{ w(U(S-S)) + \sqrt{\ln (2/p)}}{\sqrt{m_2}} + 1\right) \\&\le c' m_1\left( w(U(S-S)) + \sqrt{\ln \frac{1}{p}}\,\right) =: a'_E\le c_1 N, \end{aligned} \end{aligned}$$

(47)

will simultaneously hold with probability at least $1-p/3$, where $c, c', c_1$ are absolute constants. In (47) we have used the assumptions that $m_1 \le \sqrt{N}$ and $1/p\le e^N$ as well as the fact that $\Vert A\Vert \le m_1$ always (see Lemma A.3), and that $w(U(S-S)) \le \sqrt{N} + c''$ for an absolute constant $c''$ (see, e.g., [46, Ex. 7.5.7]). Furthermore, we note that (47) implies that ${\epsilon }/{c_1 N} \le \delta = {c' c_4 \epsilon }/{a_E'} \le {\epsilon }/{a_E}$ holds provided that, e.g., $c_4$ is chosen to be $1/c'$.

Next, Lemma A.3 with $p \leftarrow p/3$, $\epsilon \leftarrow \epsilon / 14$, ${\tilde{S}} \leftarrow {\mathcal {C}}_{\delta }$, $K \leftarrow K$ reveals that

$$\begin{aligned} {\mathcal {E}}_{(b)} :=\bigl \{A\text { is an }(\epsilon /14)\text {-JL map of }P_j {\mathcal {C}}_{\delta }\text { into }\mathbbm {R}^{m_1}\text { for all }j \in [N/m_1^2]_0\bigr \} \end{aligned}$$

will also hold with probability at least $1 - p/3$ provided that (47) holds. Here we have used the fact that ${\mathcal {N}}(S,{\epsilon }/{c_1 N}) \ge {\mathcal {N}}(S, \delta ) = |{\mathcal {C}}_{\delta }|$ when $\delta \ge \epsilon /c_1N$. As a consequence we can finally see that both assumptions (a) and (b) of Lemma A.1 with $\epsilon \leftarrow \epsilon / 14$ will hold with probability at least $1-p$ since

$$\begin{aligned} \mathbbm {P}[ {\mathcal {E}}_{(c)} \cap (47)\cap {\mathcal {E}}_{(b)}]&\ge 1 - \mathbbm {P}[ \overline{(47) \cap {\mathcal {E}}_{(b)}}]-\frac{p}{3}=\mathbbm {P}[(47) \cap {\mathcal {E}}_{(b)}] - \frac{p}{3}\\&= \mathbbm {P}[{\mathcal {E}}_{(b)} |(47)] \cdot \mathbbm {P}[(47)] -\frac{p}{3} \ge \biggl (1-\frac{p}{3}\biggr )\mathbbm {P}[ (47)] -\frac{p}{3} \\&\ge \biggl (1-\frac{p}{3}\biggr )^{2} -\frac{p}{3} > 1- p. \end{aligned}$$

Lemma A.1 now finishes the proof. The runtime result follows from Lemma 1.1. $\square$

Note that an application of Theorem A.1 requires a valid choice of $m_1$ to be made. This will effectively limit the sizes of the sets which we can embed below. In order to make the discussion of this limitation a bit easier below we can further simplify the lower bound for $m_1$ by noting that for all fixed $S \subset U(\mathbbm {R}^N)$, $K \in [1,N^{{1}/{4}})$, $\epsilon \in (0, 1/3)$, and $p \in (e^{-N},{1}/{3})$ we will have

$$\begin{aligned} \ln \frac{N}{p}\ln ^2 \left( \frac{K^2}{\epsilon }\ln \frac{N {\mathcal {N}}(S,{\epsilon }/{c_1 N})}{p}\right) \le \ln ^3 \frac{N K^2}{\epsilon p}\le c \ln ^3 \frac{N}{\epsilon p} \end{aligned}$$

for an absolute constant $c \in \mathbbm {R}^+$, provided that ${\mathcal {N}}(S,{\epsilon }/{c_1 N}) \le p e^N/N$. As a consequence, we may weaken the lower bound for $m_1$ and instead focus on the smaller interval

$$\begin{aligned} \sqrt{N} \ge m_1 \ge \frac{c''_2 K^2}{\epsilon ^2}\ln \frac{{\mathcal {N}}(S,{\epsilon }/{c_1 N})}{p}\ln ^4 \frac{N}{\epsilon p}\ge \frac{c'_2 K^2}{\epsilon ^2}\ln \frac{ N {\mathcal {N}}(S,{\epsilon }/{c_1 N})}{p}\ln ^3\frac{N}{\epsilon p} \end{aligned}$$

for simplicity. Further assuming that K is upper bounded by a universal constant below (as it will be in all subsequent applications) we can see that our smaller range for $m_1$ will be nonempty when

$$\begin{aligned} {\mathcal {N}}(S, \delta ) \le {\mathcal {N}} \biggl (S, \frac{\epsilon }{c_1 N} \biggr ) \le p e^{c \epsilon ^2 \sqrt{N}/\ln ^4({N}/{\epsilon p})} \end{aligned}$$

(48)

for a sufficiently small absolute constant $c \in \mathbbm {R}^+$. We will use (48) in place of (9) below to limit the sizes of the sets that we embed so that Theorem A.1 can always be applied with a valid minimal choice of

$$\begin{aligned} m_1 \le \frac{c_2''' K^2}{\epsilon ^2} \ln \frac{{\mathcal {N}}(S,{\epsilon }/{c_1 N}) }{p}\ln ^4\frac{N}{\epsilon p}\le \sqrt{N} \end{aligned}$$

below.

1.1 Theorem 3.4 as a Corollary of Theorem A.1

As above, we let B have, e.g., i.i.d. Rademacher entries and will choose $U\in {\mathbbm {R}}^{m_1^2\times m_1^2}$ to be, e.g., a Hadamard or DCT matrix (see, e.g., [24, Sect. 12.1]). Making either choice for U will endow A with an ${\mathcal {O}}(m_1^2\log m_1)$-time matrix vector multiply via FFT-techniques, and will also ensure that $K=\sqrt{2}$ always suffices. As a result, we note that $f(m_1)= {\mathcal {O}}(\log m_1)$ in Theorem A.1.

We may therefore apply Theorem A.1 with S as in (41). To upper bound the final embedding dimension we note that we may safely choose

$$\begin{aligned} m_2 \ge \frac{ c_3}{\epsilon ^2} \ln \frac{{\mathcal {N}}(S,{\epsilon }/{c_1 N})}{p}\ge \frac{c_3}{\epsilon ^2} \ln \frac{{\mathcal {N}}(S, \delta )}{p}. \end{aligned}$$

Furthermore, applying Lemmas 3.2 and 3.3 we can further see that

$$\begin{aligned} \biggl ( \frac{eN}{s} \biggr )^{s} \biggl ( \frac{3c_1 N}{\epsilon } \biggr )^{s} \ge {\mathcal {N}}\biggl (S, \frac{\epsilon }{c_1 N}\biggr ). \end{aligned}$$

The stated lower bound on m now follows after adjusting and simplifying constants. Finally, and most crucially, the condition it suffices for s to satisfy now also follows from (48).