Toward a unified theory of sparse dimensionality reduction in Euclidean space

Introduction

Dimensionality reduction is a ubiquitous tool across a wide array of disciplines: machine learning , high-dimensional computational geometry , privacy , compressed sensing , spectral graph theory , interior point methods for linear programming , numerical linear algebra , computational learning theory , manifold learning , motif-finding in computational biology , astronomy , and several others. Across all these disciplines one is typically faced with data that is not only massive, but each data item itself is represented as a very high-dimensional vector. For example, when learning spam classifiers a data point is an email, and it is represented as a high-dimensional vector indexed by dictionary words . In astronomy a data point could be a star, represented as a vector of light intensities measured over various points sampled in time . Dimensionality reduction techniques in such applications provide the following benefits:

Cheaper transmission of data across computing clusters.

for some norm $\|\cdot\|$. Note also that for unit vectors $x,y$, $\cos(\angle(x,y))=(1/2)(\|x\|_{2}^{2}+\|y\|_{2}^{2}-\|x-y\|_{2}^{2})$, and thus $f$ also preserves angles with additive error if it preserves Euclidean norms of points in $X\cup(X-X)$.

A powerful tool for achieving Eq. (1.1), used in nearly all the applications cited above, is the Johnson-Lindenstrauss (JL) lemma .

Furthermore, since we consider $\Phi$ chosen at random, we more specifically want

Instance-wise understanding for achieving Eq. (1.3) was first provided by Gordon , who proved that a random $\Phi$ with i.i.d. Gaussian entries satisfies Eq. (1.3) as long as $m\gtrsim(g^{2}(T)+1)/\varepsilon^{2}$, where we write $A\gtrsim B$ if $A\geq CB$ for a universal constant $C>0$. Denoting by $g$ a standard $n$-dimensional Gaussian vector, the parameter $g(T)$ is defined as the Gaussian mean width

Although Gordon’s theorem gives a good understanding for $m$ in most scenarios, it suffers from the fact that it analyzes a dense random $\Phi$, which means that performing the dimensionality reduction $x\mapsto\Phi x$ is dense matrix-vector multiplication, and is thus slow. For example, in some numerical linear algebra applications (such as least squares regression ), multiplying a dense unstructured $\Phi$ with the input turns out to be slower than obtaining the solution of the original, high-dimensional problem! In compressed sensing, certain iterative recovery algorithms such as CoSamp and Iterative Hard Thresholding involve repeated multiplications by $\Phi$ and $\Phi^{*}$, the conjugate transpose of $\Phi$, and thus $\Phi$ supporting fast matrix-vector multiply are desirable in such applications as well.

The first work to provide $\Phi$ with small $m$ supporting faster multiplication is the Fast Johnson-Lindenstrauss Transform (FJLT) of for finite $T$. The value of $m$ was still $O(\varepsilon^{-2}\log|T|)$, with the time to multiply $\Phi x$ being $O(n\log n+m^{3})$. later gave an improved construction with time $O(n\log n+m^{2+\gamma})$ for any small constant $\gamma>0$. Most recently several works gave nearly linear embedding time in $n$, independent of $m$, at the expense of increasing $m$ by a $(\log n)^{c}$ factor . In all these works $\Phi$ is the product of some number of very sparse matrices and Fourier matrices, with the speed coming from the Fast Fourier Transform (FFT) . It is also known that this FFT-based approach can be used to obtain fast RIP matrices for compressed sensing and fast oblivious subspace embeddings for numerical linear algebra applications (see also for refined analyses in the latter case).

Another line of work, initiated in and greatly advanced in , sought fast embedding time by making $\Phi$ sparse. If $\Phi$ is drawn from a distribution over matrices having at most $s$ non-zeroes per column, then $\Phi x$ can be computed in time $s\cdot\|x\|_{0}$. After some initial improvements , the best known achievable value of $s$ to date for the JL lemma while still maintaining $m\lesssim\varepsilon^{-2}\log|T|$ is the sparse Johnson-Lindenstrauss Transform (SJLT) of , achieving $s\lesssim\varepsilon^{-1}\log|T|\lesssim\varepsilon m$. Furthermore, an example of a set $T$ exists which requires this bound on $s$ up to $O(\log(1/\varepsilon))$ for any linear JL map . Note however that, again, this is an understanding of the worst-case parameter settings over all $T$.

Let $T\subseteq S^{n-1}$ and $\Phi$ be the SJLT. What relationship must $s,m$ satisfy, in terms of the geometry of $T$, to ensure (1.3)?

We also note that while the FFT-based and sparse $\Phi$ approaches seem orthogonal at first glance, the two are actually connected, as pointed out before . The FJLT sets $\Phi=SP$ where $P$ is some random preconditioning matrix that makes $T$ “nice” with high probability, and $S$ is a random sparse matrix. We point out that although the SJLT is not the same as the matrix $S$ typically used in the FFT-based literature, one could replace $S$ with the SJLT and hope for similar algorithmic outcome if $s$ is small: nearly linear embedding time.

We provide a general theorem which answers Question 2. Specifically, for every $T\subseteq S^{n-1}$ analyzed in previous work that we apply our general theorem to here, we either (1) qualitatively recover or improve the previous best known result, or (2) prove the first non-trivial result for dimensionality reduction with sparse $\Phi$. We say “qualitatively” since applying our general theorem to these applications loses a factor of $\log^{c}(n/\varepsilon)$ in $m$ and $\log^{c}(n/\varepsilon)/\varepsilon$ in $s$.

In particular for (2), our work is the first to imply that non-trivially sparse dimensionality reducing linear maps can be applied for gain in model-based compressed sensing , manifold learning , and constrained least squares problems such as the popular Lasso .

Specifically, we prove the following theorem.

Let $T\subset S^{n-1}$ and $\Phi$ be an SJLT with column sparsity $s$. Define the complexity parameter

where $(g_{j})$ are i.i.d. standard Gaussian and $(\eta_{j})$ i.i.d. Bernoulli with mean $qs/(m\log s)$. If

Then (1.3) holds as long as $s,m$ furthermore satisfy the condition

The complexity parameter $\kappa(T)$ may seem daunting at first, but Section 8 shows it can be controlled quite easily for all the $T$ we have come across in applications.

1. Applications

Here we describe various $T$ and their importance in certain applications. Then we state the consequences that arise from our theorem. In order to highlight the qualitative understanding arising from our work, we introduce the notation $A\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}B$ if $A\leq B\cdot\varepsilon^{-2}(\log n)^{c}$. A summary of our bounds is in Figure 1.

Our theorem implies $s,m\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}\log|T|$ suffices in general, and $s\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}1+(\alpha\log|T|)^{2},m\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}\log|T|$ in the latter case, qualitatively matching the above.

Our theorem implies that $s\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}1$ and $m\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}d$ suffices to satisfy Eq. (1.3), which is qualitatively correct. Furthermore, a subset of our techniques reveals that if the maximum incoherence $\max_{1\leq i\leq n}\|P_{E}e_{i}\|_{2}$ is at most $\mathop{poly}(\varepsilon/\log n)$, then $s=1$ suffices (Theorem 5). This was not known in previous work. A random $d$-dimensional subspace has incoherence $\sqrt{d/n}$ w.h.p. for $d\gtrsim\log n$ by the JL lemma, and thus is very incoherent if $n\gg d$.

Our work also applies to such $T$ (and we further show the SJLT with small $s,m$ satisfies the second condition required for approximate constrained least squares; see Theorem 16). For example for the Lasso, we show that again it suffices that

That is, the sparsity of $\Phi$ need only depend on the largest entry in $A$ as opposed to the largest column norm in $A$. The former can be much smaller.

Baraniuk and Wakin proposed using dimensionality-reducing maps to first map $\mathcal{M}$ to $\Phi\mathcal{M}$ and then learn the parameters of interest in the reduced space (for improved speed). Sharper analyses were later given in . Of interest are both that (1) any $C^{1}$ curve in $\mathcal{M}$ should have length approximately preserved in $\Phi\mathcal{M}$, and (2) $\Phi$ should be a manifold embedding, in the sense that all $C^{1}$ curves $\gamma^{\prime}\in\Phi\mathcal{M}$ should satisfy that the preimage of $\gamma^{\prime}$ (in $\mathcal{M}$) is a $C^{1}$ curve in $\mathcal{M}$. Then by (1) and (2), geodesic distances are preserved by $\Phi$.

We want $\Phi$ satisfying $(1-\varepsilon)|\gamma|\leq|\Phi(\gamma)|\leq(1+\varepsilon)|\gamma|$ for all $C^{1}$ curves $\gamma\subset\mathcal{M}$. Here $|\cdot|$ is curve length. To obtain this, it suffices that $\Phi$ satisfy Eq. (1.2) for $T=\bigcup_{x\in\mathcal{M}}E_{x}\cap S^{n-1}$ , an infinite union of subspaces. Using this observation, showed this property is satisfied for $s=m\lesssim d/\varepsilon^{2}$ with a dense matrix of subgaussian entries. For $F$ as given above, preservation of geodesic distances is also satisfied for this $m$.

Our main theorem implies that to preserve curve lengths one can set $m\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}d$ for $s\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}1+(\alpha d)^{2}$, where $\alpha$ is the largest incoherence of any tangent space $E_{x}$ for $x\in\mathcal{M}$. That is, non-trivial sparsity with $m\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}d$ is possible for any $\alpha\ll 1/\sqrt{d}$. Furthermore, we show that this is optimal by constructing a manifold with maximum incoherence of a tangent space approximately $1/\sqrt{d}$ such that any linear map $\Phi$ preserving curve lengths with $m\mathbin{\begin{subarray}{c}>\\ *\end{subarray}}d$ must have $s\mathbin{\begin{subarray}{c}>\\ *\end{subarray}}d$ (see Remark 20). We also show that $\Phi$ is a manifold embedding with large probability if the weaker condition $m\mathbin{\begin{subarray}{c}>\\ *\end{subarray}}d,s\mathbin{\begin{subarray}{c}>\\ *\end{subarray}}1$ is satisfied. Combining these observations, we see that for the SJLT to preserve geodesic distances it suffices to set $m\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}d$ and $s\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}1+(\alpha d)^{2}$.

As seen above, not only does our answer to Question 2 qualitatively explain all known results, but it gives new results not known before with implications in numerical linear algebra, compressed sensing (model-based, and with incoherent dictionaries), constrained least squares, and manifold learning. We also believe it is possible for future work to sharpen our analyses to give asymptotically correct parameters for all the applications; see the discussion in Section 9.

We now end the introduction with an outline for the remainder. Section 2 defines the notation for the rest of the paper. Section 3 provides an overview of the proof of our main theorem, Theorem 3. Section 4 is a warmup that applies a subset of the proof ideas for Theorem 3 to the special case where $T=E\cap S^{n-1}$, $E$ a linear subspace of dimension $d$. In fact the proof of our main theorem reduces the case of general $T$ to several linear subspaces of varying dimensions, and thus this case serves as a useful warmup. Section 5 applies a different subset of our proof ideas to the special case where the norm $|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|_{T}$ defined by $|\kern-1.07639pt|\kern-1.07639pt|y|\kern-1.07639pt|\kern-1.07639pt|_{T}=\sup_{x\in T}|\left\langle x,y\right\rangle|$ has a small type-$2$ constant, which is relevant for analyzing the FFT-based approaches to RIP matrices. Section 6 shows how similar ideas can be applied to constrained least squares problems, such as Lasso. Section 7 states and proves our most general theorem for arbitrary $T$. Section 8 shows how to apply Theorem 3 to obtain good bounds for various $T$, albeit losing a $\log^{c}(n/\varepsilon)$ factor in $m$ and a $\log^{c}(n/\varepsilon)/\varepsilon$ factor in $s$ as mentioned above. Finally, Section 9 discusses avenues for future work.

In the appendix, in Appendix A for the benefit of the reader we review many probabilistic tools that are used throughout this work . Appendix B reviews some introductory material related to convex analysis, which is helpful for understanding Section 6 on constrained least squares problems. In Appendix C we also give a direct analysis for using the FJLT for sketching constrained least squares programs, providing quantitative benefits over some analyses in .

Preliminaries

Here $\mathcal{N}(S,\rho,u)$ denotes the minimum number of $\rho$-balls of radius $u$ centered at points in $S$ required to cover $S$. If $\rho$ corresponds to a (semi-)norm $\|\cdot\|_{X}$, then we write $\mathcal{N}(S,\|\cdot\|_{X},u)$ instead of $\mathcal{N}(S,\rho_{X},u)$.

For fixed $j$ the $\delta_{ij}$ are negatively correlated, i.e.

For any fixed $j$ there are exactly $s$ nonzero $\delta_{ij}$, i.e., $\sum_{i=1}^{m}\delta_{ij}=s$;

The vectors $(\delta_{ij})_{i=1}^{m}$ are independent across different $1\leq j\leq n$.

We emphasize that the $\sigma_{ij}$ and $\delta_{ij}$ are independent, as they are defined on different probability spaces. The sparse Johnson-Lindenstrauss transform $\Phi$ with column sparsity $s$, or SJLT for short, is defined by

The work gives two implementations of such a $\Phi$ satisfying the above conditions. In one example, the columns are independent, and in each column we choose exactly $s$ locations uniformly at random, without replacement, to specify the $\delta_{ij}$. The other example is essentially the CountSketch of . In this implementation, the rows of $\Phi$ are partitioned arbitrarily into $s$ groups of size $m/s$ each. Then each column of $\Phi$ is chosen independently, where in each column and for each block we pick a random row in that block to be non-zero for that column (the rest are zero).

We say that $\Phi$ is an $\varepsilon$-restricted isometry on $T$ if Eq. (1.2) holds. We define

as the restricted isometry constant of $\Phi$ on $T$. In the following we will be interested in estimating $\varepsilon_{\Phi,T}$. For this purpose, we use the following $L^{p}$-bound for the supremum of a second order Rademacher chaos from (see [42, Theorem 6.5] for the refinement stated here).

With this definition, we have for any $x,y\in T$,

Taking $L_{p}(\Omega_{\delta})$-norms on both sides yields

Unless explicitly stated otherwise, from here on $\Phi$ always denotes the SJLT with $s$ non-zeroes per column.

Overview of proof of main theorem

for a Gaussian vector $g$. From this point onward one can arrive at a result using the non-commutative Khintchine inequality and other standard Gaussian concentration arguments (see appendix).

Finally we are in a position to apply dual Sudakov minoration to the right hand side of Eq. (3.3), after which point we apply various concentration arguments to yield our main theorem.

The case of a linear subspace

which is sometimes referred to as the incoherence $\mu(E)$ of $E$.

For any $p\geq\log m$ and any $0<\epsilon<1$,

then Eq. (1.2) holds with probability at least $1-\eta$.

By dual Sudakov minoration (Lemma 29 in Appendix A)

where Eq. (4.5) used Gaussian concentration of Lipschitz functions (cf. Eq. (4.1)), noting that $g\mapsto\|U^{(i)}g\|_{2}$ is $\|U^{(i)}\|$-Lipschitz.

Since $\|\cdot\|_{\delta}\leq(1/\sqrt{s})\|\cdot\|_{2}$, we can use for small $t$ the bound (cf. Eq. (A.6))

Using Eq. (4.6) for small $t$ and noting $\|U^{(i)}\|_{F}=(\sum_{j=1}^{n}\delta_{ij}\|P_{E}e_{j}\|_{2}^{2})^{1/2}$ for $P_{E}$ the orthogonal projection onto $E$, Eq. (2.2) yields for $t^{*}=(\epsilon/d)/\log(d/\epsilon)$

We estimate the first non-trivial term on the right hand side. Since $p\geq\log m$,

Note that for fixed $i$, the $(\delta_{ij})_{1\leq j\leq n}$ are i.i.d. variables of mean $s/m$ and therefore

Let $(r_{j})_{1\leq j\leq n}$ be a vector of independent Rademachers. By symmetrization (Eq. (A.4)) and Khintchine’s inequality (Eq. (A.2)),

We now estimate the last term on the right hand side of Eq. (4.8). As $p\geq\log m$,

If $u_{j}$ denotes the $j$th row of $U$, then

By symmetrization and the non-commutative Khintchine inequality (cf. Eq. (A.3)),

Solving this quadratic inequality, we find

Applying this estimate together with Eq. (4.10) in Eq. (4.8) yields the asserted estimate in Eq. (4.2). For the second assertion, note by Cauchy-Schwarz that

and Eq. (4.3) immediately follows from Eq. (4.10).

To prove the final assertion, we combine (2.10), Eq. (4.2) and Eq. (4.3) to obtain

Now apply Lemma 27 of Appendix A to obtain, for any $w\geq\log m$,

Theorem 5 recovers a similar result in but via a different method, less logarithmic factors in the setting of $m$, and the revelation that $s$ can be taken smaller if all the leverage scores $\|P_{E}e_{j}\|_{2}$ are small (note if $\|P_{E}e_{j}\|_{2}\ll(\log d\cdot\log m)^{-1}$ for all $j$, we may take $s=1$, though this is not true in general). Our dependence on $1/\varepsilon$ in $s$ is quadratic instead of the linear dependence in , but as stated earlier, in most applications of OSE’s $\varepsilon$ is taken a constant.

The type-222 case

Recall that the type-$2$ constant $T_{2}(\|\cdot\|)$ of a semi-norm $\|\cdot\|$ is defined as the best constant (if it exists) such that the inequality

holds, for all finite systems of vectors $\{x_{\alpha}\}$ and i.i.d. standard Gaussian $(g_{\alpha})$.

Given $T\subset S^{n-1}$, define the semi-norm

It will be convenient to use the following notation. For $i=1,\ldots,m$ we let $J_{i}$ be the set of ‘active’ indices, i.e., $J_{i}=\{j=1,\ldots,n:\delta_{ij}=1\}$. We can then write

where we abuse notation and let $P_{J_{i}}$ denote orthogonal projection onto the coordinate subspace specified by $J_{i}$.

where $T_{2}(\|\cdot\|)$ is the type-$2$ constant and for $1\leq i\leq m$,

Note also that $d_{\delta}(T)$ can be bounded as

Replacing $|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|_{T}$ by a stronger norm $\|\cdot\|\geq|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|_{T}$ in this lemma may reduce the type-$2$ constant. The application to $k$-sparse vectors will illustrate this.

By Eq. (2.2), to bound $\gamma_{2}(T,\|\cdot\|_{\delta})$ it suffices to evaluate the covering numbers $\mathcal{N}(T,\|\cdot\|_{\delta},t)$ for $t<d_{\delta}^{*}(T)/\sqrt{s}$, where we set

where $A\lesssim T_{2}(\|\cdot\|_{\delta})^{2}\lesssim\log m$ (by (5.2)) and we used that

To estimate the right hand side we use the following consequence of Maurey’s lemma (Lemma 31 of Appendix A).

It suffices to prove the result for $R=1$, the general case then follows by considering $R^{-1}\Omega$. For each positive integer $k$, let $\Omega_{k}\subset\Omega$ be a finite set satisfying

Given $x\in\Omega$, denote $x_{k}\in\Omega_{k}$ a sequence s.t. $\|x-x_{k}\|<2^{-k}$. Then, setting $y_{0}=x_{0}$, $y_{k}=x_{k}-x_{k-1}$, we obtain

Since $|\{k\ :\ \epsilon/2<2^{-k}\leq 1\}|\leq\log(2/\epsilon)$, we obtain from the preceding,

and Eq. (5.5) follows. This proves the claim. ∎

Write $d_{\|\cdot\|}:=d_{\|\cdot\|}(\cup_{i=1}^{m}B_{J_{i}})$ for brevity. Applying Claim 9 with $\Omega=\cup_{i=1}^{m}B_{J_{i}}$, $\epsilon=t\sqrt{s}$, and the dominating semi-norm $\|\cdot\|\geq|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|_{T}$ to the right hand side of Eq. (5.4), we find

Using the dual Sudakov inequality (Lemma 29 of Appendix A) we arrive at

We now apply Eq. (5.11) for $(sn)^{-1/2}d_{\|\cdot\|}\leq t<s^{-1/2}d_{\|\cdot\|}$ and the estimate (cf. Eq. (A.6))

for $0<t<(sn)^{-1/2}d_{\|\cdot\|}$, respectively, in Eq. (2.2). A straightforward computation, similar to Eq. (4.7), yields the result. ∎

Let $\|x\|_{0}$ denote the number of non-zero entries of $x$ and set

then with probability at least $1-\eta$ we have

and one can readily calculate that $T_{2}(|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|_{K})\lesssim\sqrt{\log n}$ and $d_{|\kern-0.75346pt|\kern-0.75346pt|\cdot|\kern-0.75346pt|\kern-0.75346pt|_{K}}(\cup_{i=1}^{m}B_{J_{i}})\leq 1$. We apply Lemma 7 with $\|\cdot\|=|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|_{K}$. Note that for every $1\leq i\leq m$,

By solving this quadratic inequality, we find

Combine this bound with Eq. (5.1) and Eq. (2.10) to arrive at

Since $p\geq\log m$ was arbitrary, the result now follows from Lemma 27. ∎

Sketching constrained least squares programs

and let $\hat{x}$ be a minimizer of the associated sketched program

We denote the tangent cone of $\mathcal{C}$ at a point $x$ by $T_{\mathcal{C}}(x)$ (see Appendix B for a definition). The first statement in the following lemma is [85, Lemma 1]. For the convenience of the reader we provide a proof, which is in essence the same as in , with the second case (when $x_{*}$ is a global minimizer) being a slight modification of the proof there. In what follows we assume $Ax_{*}\neq b$, since otherwise $f(\hat{x})=f(x_{*})=0$.

Define $u=(Ax_{*}-b)/\|Ax_{*}-b\|_{2}$ and set $Z_{1}=Z_{1}(A,\Phi,T_{\mathcal{C}}(x_{*}))$ and $Z_{2}=Z_{2}(A,\Phi,T_{\mathcal{C}}(x_{*}),u)$. Then,

If $x_{*}$ is a global minimizer of $f$, then

Set $e=\hat{x}-x_{*}\in T_{\mathcal{C}}(x_{*})$ and $w=b-Ax_{*}$. By optimality of $x_{*}$, for any $x\in\mathcal{C}$,

In particular, taking $x=\hat{x}$ gives $\langle w,Ae\rangle\leq 0$. As a consequence,

By optimality of $\hat{x}$, for any $x\in\mathcal{C}$,

If $x_{*}$ is a global minimizer of $f$, then $\nabla f(x_{*})=0$ and therefore $\langle w,Ae\rangle=0$ (a similar observation to [90, Theorem 12]). This yields the second assertion. ∎

Clearly, if $\Phi$ satisfies (1.2) for $T=AT_{\mathcal{C}}(x_{*})\cap S^{n-1}$ then $Z_{1}\geq 1-\varepsilon$. We do not immediately obtain an upper bound for $Z_{2}$, however, as $u$ is in general not in $AT_{\mathcal{C}}(x_{*})\cap S^{n-1}$. We mend this using the observation in Lemma 13. For its proof we recall a chaining result from . Let $(T,\rho)$ be a semi-metric space. Recall that a real-valued process $(X_{t})_{t\in T}$ is called subgaussian if for all $s,t\in T$,

The following result is a special case of [42, Theorem 3.2].

If $(X_{t})_{t\in T}$ is subgaussian, then for any $t_{0}\in T$ and $1\leq p<\infty$,

In particular, if $T$ contains $n$ elements, then

Let $\sigma^{\prime}$ be an independent copy of $\sigma$. By decoupling (see (A.5)),

For any $v_{1},v_{2}\in T$, Hoeffding’s inequality implies that for all $w\geq 0$

and therefore $v\mapsto\sigma^{*}A_{\delta,u}^{*}A_{\delta,v}\sigma^{\prime}$ is a subgaussian process. By Lemma 12 (and (2.8)),

Taking the $L_{p}(\Omega_{\sigma})$-norm on both sides and using Lemma 28 of Appendix A we find

Now take the $L_{p}(\Omega_{\delta})$-norm on both sides to obtain the result. ∎

and $\eta\leq\frac{1}{m}$. Then, with probability at least $1-\eta$,

Applying Lemma 27 (and setting $w=\log(\eta^{-1})$ in (A.1)) shows that $Z_{2}\leq\sqrt{\varepsilon}$ with probability at least $1-\eta$. The second statement in Lemma 11 now implies that with probability at least $1-2\eta$,

To see the last inequality, note that it is equivalent to

Clearly this is satisfied for $\varepsilon$ small enough (since then $-\varepsilon$ is the leading term). In fact, one can verify by calculus that this holds for $\varepsilon\leq 1/10$, which we may assume without loss of generality. ∎

If $\Phi$ is a full random sign matrix (i.e., $s=m$) then it follows from our proof that (6.4) holds with probability at least $1-\eta$ if

This bound on $m$ is new, and was also recently shown in . Previous works allowed either $m\gtrsim\varepsilon^{-2}(r(A)+\log(\eta^{-1}))$ or $m\gtrsim\varepsilon^{-1}r(A)\log(\eta^{-1})$. Theorem 14 substantially improves $s$ while maintaining $m$ up to logarithmic factors.

where $\alpha=(\log n)^{6}(\log m)^{2}(\log b)^{2}$.

We deduce the assertion from Lemma 7. By Hölder’s inequality,

and therefore $T_{2}(\|\cdot\|)\leq(\log b)^{1/2}$. Similarly,

and for any $1\leq i\leq m$ and $x\in B_{J_{i}}$,

We now apply Lemma 7 for $T=A\mathcal{K}\cap S^{n-1}$ and subsequently take $L_{p}(\Omega_{\delta})$-norms to conclude that for any $p\geq\log m$,

Putting the last two displays together we find a quadratic inequality. By solving it, we arrive at

Combining this estimate with (6.2) yields the assertion. ∎

and $\eta\leq\frac{1}{m}$. Then, with probability at least $1-\eta$,

Set $T=AT_{\mathcal{C}}(x_{*})\cap S^{n-1}$, $Z_{1}=Z_{1}(A,\Phi,T_{\mathcal{C}}(x_{*}))$ and $Z_{2}=Z_{2}(A,\Phi,T_{\mathcal{C}}(x_{*}),u)$. We apply Eq. (5), Eq. (6.2) and Eq. (6.2) to find for any $p\geq\log m$,

Similarly, using Lemma 13 (with $Z(u):=Z_{2}(A,\Phi,T_{\mathcal{C}}(x_{*}),u)$) we find

Now apply Lemma 27 (with $w=\log(\eta^{-1})$) to conclude that with probability at least $1-\eta$ we have $Z_{2}\leq\varepsilon$ and $Z_{1}\geq 1-\varepsilon$ under the assumptions on $m$ and $s$. Lemma 11 now implies that

Suppose that $x_{*}$ is $k$-block sparse and $\|x_{*}\|_{2,1}=R$. Define

Set $\alpha=(\log n)^{6}(\log m)^{2}(\log b)^{2}$. Assume that

and $\eta\leq\frac{1}{m}$. Then with probability at least $1-\eta$

As calculated in Example 33 of Appendix B, every $x\in T_{\mathcal{C}}(x_{*})$ satisfies $\|x\|_{2,1}^{2}\leq 4k\|x\|_{2}^{2}$. If moreover $\|Ax\|_{2}=1$, then

For a dense random sign matrix $\Phi$, it follows from [85, Theorem 1] that the result in Corollary 17 holds under the condition

Thus, our result shows that one can substantially increase the sparsity in the matrix $\Phi$, while maintaining the embedding dimension $m$ (up to logarithmic factors).

Let us now specialize our results to the case $D=1$, which corresponds to the Lasso. In this case, if we let $A_{k}$ denote the columns of $A$,

the largest entry of the matrix. The first norm can be significantly larger than the second. For example, if $A$ is filled with $\pm 1$ entries, then

A similar result for the fast J-L transform, but with a worse dependence of $m$ on the matrix $A$, was obtained in . For completeness, we will show in Appendix C that the fast J-L transform in fact satisfies similar results as Theorem 16 and Corollary 17, with the essentially the same dependence of $m$ on $A$.

Proof of the main theorem

After having seen instantiations of various subsets of our ideas for specific applications (linear subspaces, $|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|_{T}$ of small type-2 constant, and closed convex cones), we now prove the main theorem of this work, Theorem 3. Our starting point is the observation that inequality Eq. (5.4), i.e.,

holds in full generality. We will need the following replacement of Claim 9.

with $y_{i}\in B_{J_{i}}$, $\lambda_{i}\geq 0$, $\sum_{i}\lambda_{i}=1$, $k\lesssim 1/\epsilon^{2}$. Firstly, we may dismiss the coefficients $\lambda_{i}<\epsilon^{3}$. Indeed, let $S=\{i\ :\ \lambda_{i}<\epsilon^{3}\}$ and set $\hat{y}=\sum_{i\in S}\lambda_{i}y_{i}$. Then,

is an $\epsilon$-net of cardinality at most

Next, we analyze further the set $(1/k)\sum_{i\in A}B_{J_{i}}$ for some $k\lesssim 1/\epsilon^{2}$ ($\epsilon>0$ will be fixed later). The elements of $(1/k)\sum_{i\in A}B_{J_{i}}$ are of the form

Define for $\alpha=1,\ldots,\log(\min\{k,s\})$ the set

where the first term in the $\min$ is a consequence of Markov’s inequality, and the second term follows by using that

Hence, denoting $B_{U_{\alpha}}:=\{\sum_{j\in U_{\alpha}}x_{j}e_{j}\ :\ \sum_{j\in U_{\alpha}}|x_{j}|^{2}\leq 1\}$,

By the dual Sudakov inequality (Lemma 29 of Appendix A),

Applying Eq. (7.12) to Eq. (7.1), taking $\epsilon\simeq\sqrt{s}t$, gives

Using this bound for large $t$ and the elementary bound in Eq. (A.6) for small $t$ in Eq. (2.2), we obtain

We split the sum over $\alpha$ into three different parts. Firstly,

Note that the first term on the right hand side is bounded by

To bound the second term, we take expectations with respect to $\delta$ and find for p_{k}=k\log\Big{(}\frac{m}{sk}\Big{)}

Finally, consider the $\alpha$ with $2^{\alpha}>10\log n$. Since $|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|_{T}\leq\|\cdot\|_{2}$,

By Eq. (7.10), the intensity of $U_{\alpha}$ is bounded by $2^{-2^{\alpha}}$ and therefore,

where $q_{k}\simeq k\log(m/k)$ and the $\zeta_{j}$ are i.i.d. $\{0,1\}$-valued with mean $2^{-2^{\alpha}}$. Since $\sum_{j}\zeta_{j}$ is binomially distributed, we find using that $2^{\alpha}>10\log n$,

By combining Eq. (7.13), Eq. (7), Eq. (7.15), Eq. (7), and Eq. (7.20) we obtain

with $\eta_{j}$ i.i.d. Bernoulli with mean $qs/(m\log s)$.

Example applications of main theorem

In this section we use our main theorem to give explicit conditions under which

for several interesting sets $T\subset S^{n-1}$. This amounts to computing an upper bound for the parameters $\gamma_{2}(T,\|\cdot\|_{2})$ and

We focus on the latter two and refer to for details on how to estimate $\gamma_{2}(T,\|\cdot\|_{2})$. Note, however, that $\gamma_{2}(T,\|\cdot\|_{2})\lesssim(m\log s)^{1/2}\kappa(T)$. Indeed, take $q=\frac{m}{s}\log s$ in Eq. (8.1) and note that the $\eta_{j}$ are identically equal to $1$ in this case. This gives

Thus, if we ignore logarithmic factors, it suffices to bound $\kappa(T)$.

with $\eta_{j}\in\{0,1\}$ i.i.d. of mean $qs/(m\log s)$. Using Khintchine’s inequality,

Eq. (7.22) and Eq. (7.23) then give conditions

2. k𝑘k-sparse vectors

Consider next the application from Section 5.1, replacing $T$ by $K$ given by Eq. (5.14). Thus $\gamma_{2}(K)\lesssim\sqrt{k\log n}$ and Eq. (7.24) is bounded by

3. Flat vectors

Let $T\subseteq S^{n-1}$ be finite with $\|x\|_{\infty}\leq\alpha$ for all $x\in T$. Then by a similar calculation as in (4.10),

Since $\gamma_{2}(T,\|\cdot\|_{2})\lesssim\sqrt{\log|T|}$ we find the conditions

which is qualitatively similar to [72, Theorem 4.1].

4. Finite collection of subspaces

In this case, $\gamma_{2}(T,\|\cdot\|_{2})\lesssim\sqrt{d}+\sqrt{\log N}$. For the duration of the next two sections, we define

Recall that $\max_{j}\|P_{E}e_{j}\|_{2}$ is referred to as the incoherence of $E$, and thus $\sqrt{d/n}\leq\alpha\leq 1$ (cf. Remark 6) is the maximum incoherence in $\Theta$.

To estimate $\kappa(T)$, consider the collection $\mathcal{A}$ of operators $A=\sum_{j}(P_{E}e_{j})\otimes e_{j}$, $E\in\Theta$. Fix $\eta$ and define $R_{\eta}x=\sum_{j}\eta_{j}x_{j}e_{j}$. Then applying [62, Theorem 3.5] to $\mathcal{A}R_{\eta}$,

By (see the formulation in [95, Proposition 7]),

Taking $\varrho=\frac{qs}{m\log s}$, it follows that

To estimate $\kappa(T)$, we need to bound

First, by Eq. (8.3) and denoting $q_{1}=q+\log N$,

and hence, applying Eq. (8.19) with $p=q+2\log n+\log N$

Hence in this application (assuming $\log N\geq\log n$),

Notice that $s$ depends only on $|\Theta|$ and not on the dimension $d$. Thus this bound is of interest when $\log|\Theta|$ is small compared with $d$.

4.2. Collection of coherent subspaces

We can also obtain a bound on $s$ that does not improve for small $\alpha$, but has linear dependence on $\log N$. Here we will not rely on . As described in Section 1, this setting has applications to model-based compressed sensing. For example, for approximate recovery of block-sparse signals using the notation of Section 1, our bounds will show that a measurement matrix $\Phi$ may have $m\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}kb+k\log(n/k)$, $s\mathbin{\begin{subarray}{c}<\\ *\end{subarray}}k\log(n/k)$ and allow for efficient recovery. This is non-trivial if the number of blocks satisfies $b\mathbin{\begin{subarray}{c}>\\ *\end{subarray}}\log(n/k)$.

since certainly $\|AR_{\eta}\|\leq\|A\|\leq 1$. Hence

leading to the following bound on $\kappa(T)$

Instead of (8.26), (8.27), one may impose the conditions

We remark that previous work which achieved $m\approx d/\varepsilon^{2}$ for small $s$ had worse dependence on $\log N$: in particular $s\gtrsim(\log N)^{3},m\gtrsim(\log N)^{6}$. In fact, Conjecture 14 of if true would imply that the correct dependence on $N$ in both $m$ and $s$ should be $\log N$ (which is optimal due to known lower bounds for the Johnson-Lindenstrauss lemma, i.e., the special case $d=1$). We thus have shown that this implication is indeed true.

5. Possibly infinite collection of subspaces

Fix some parameter $\varepsilon_{0}>0$ and let $\Theta_{1}\subset\Theta$ be a finite subset such that

where $x_{1}\in T_{1}$ and $x_{2}\in B_{E}+B_{E^{\prime}}$, $\|x_{2}\|_{2}\leq\varepsilon_{0}$. Hence $x_{2}\in T_{2}$ with

For $t<\varepsilon_{0}$, we estimate $\mathcal{N}(T_{2},\|\cdot\|_{2},t)$. Let $\Theta_{t}\subset\Theta$ satisfy

By Eq. (A.6), for each $E^{\prime}\in\Theta_{t}$ we can find $\xi_{E^{\prime}}\subset B_{E^{\prime}}$ such that

Also, for $x\in T_{2}$, $x=y+z\in B_{E}+B_{F}$ and $E^{\prime},F^{\prime}\in\Theta_{t}$ satisfying

and we get for $t<\varepsilon_{0}$ (otherwise $\eqref{eq:22c}=0$)

Using the decomposition Eq. (8.33) and the bound Eq. (8.25) for the contribution of $T_{1}$, we find

with $(\eta_{j})\in\{0,1\}$ i.i.d. of mean $\frac{qs}{m\log s}$.

Estimate by the contraction principle , the Gaussian concentration for Lipschitz functions (Eq. (4.1)), and Dudley’s inequality Eq. (2.2)

where in the final step we used Eq. (8.38).

Summarizing, the conditions on $m$ and $s$ are as follows (for any $\varepsilon_{0}>0$)

6. Manifolds

for any $C^{1}$-curve $\gamma\subset\mathcal{M}$, where $|\cdot|$ denotes curve length. Note that Eq. (8.44) is equivalent to requiring

for any tangent vector $v$ of $\mathcal{M}$ at a point $x\in\mathcal{M}$. Denote by

the tangent bundle of $\mathcal{M}$, to which we apply the estimates on $m,s$ obtained above. By assumption,

so that for $0\leq t\leq 1/2$ by Eq. (A.6),

to make the below of interest (otherwise apply the result of ). Taking $\varepsilon_{0}=\alpha\sqrt{d}$ in (8.42), (8.43), it follows that Eq. (8.44) may be ensured under parameter conditions

Thus for $\alpha=o(1/\sqrt{d})$, the condition on $s$ becomes non-trivial. Recall from Remark 6 that $\alpha\geq\sqrt{d/n}$ and therefore the $\log(1/(\alpha\sqrt{d}))$ term in Eq. (8.48) is at most $\log n$.

The second statement follows from requiring

If $\alpha\geq 1/\sqrt{d}$, then necessarily $s\gg d$ in Eq. (8.49) (up to polylogarithmic factors). Thus the manifold case is very different from the case of linear subspaces. We sketch a construction to demonstrate this.

Thus by construction, the summands in Eq. (8.53) are disjointly supported functions of $x$. Clearly

In view of Eq. (8.55), $F$ satisfies conditions (8.50),(8.51). Also, by (8.54),(8.56)

where we used Eq. (8.52). Thus $\gamma$ is a $C^{1}$-curve in $\mathcal{M}$ and

Let $\Phi$ be a sparse $m\times 2n$ matrix for which Eq. (8.44) holds. Then $\Phi$ has to satisfy in particular

for all vectors $\eta$ of the form Eq. (8.60). But if $m<n/d$, Eq. (8.61) implies that $s\geq k/400\gtrsim d/\log n$. On the other hand, Eq. (8.57) gives

In this section we show that not only do sparse maps preserve curve lengths on manifolds, but in fact they preserve geodesic distances.

with probability (with respect to $\Phi$) at least

Fix $I\subset\{1,\ldots,m\}$, $|I|\leq r_{1}$ and assume $\sum_{j}\Phi_{ij}^{2}x_{j}^{2}<1/s$ for $i\notin I$. This means that for any $j\in J$, $S=\mathbin{\stackrel{{\scriptstyle\rm def}}{{=}}}\{i;\Phi_{ij}\neq 0\}\subset I$. The probability (with respect to $\Phi$) that $\{i;\Phi_{ij}\neq 0\}\subset I$ (with $j$ fixed) is (by Eq. (2.3))

Since for different $j$ the events are independent, it follows the probability that

is bounded by $((e|I|/m)^{s})^{r}\leq(er_{1}/m)^{sr}$. Taking a union bound over all $I\subset\{1,\ldots,m\},|I|\leq r_{1}$ gives by the choice of $r_{1}$

This is a consequence of the Paley-Zygmund inequality, see e.g. [18, Theorem 3.6].

We may assume that $\sum\Phi_{ij}^{2}x_{j}^{2}\geq 1/s$ for $i$ in a subset $I\subset\{1,\ldots,m\}$, $|I|\geq r_{1}$. Exploiting the random signs of $\Phi_{ij}$, we find by Eq. (8.64) for each $i\in I$

If $\|\Phi x\|_{2}<1/(2\sqrt{s})$, then $|\sum_{j}\Phi_{ij}x_{j}|<1/(2\sqrt{s})$ for all $i$, in particular for all $i\in I$. By Eq. (8.66) the probability for this event is at most

Each $x\in\xi$ has a decomposition $x=x^{\prime}+x^{\prime\prime}$, $x^{\prime}\in\xi^{\prime}$ and there is a set $J=J_{x^{\prime}}\subset\{1,\ldots,n\}$, $|J|\geq r$ so that $|x_{j}^{\prime}|\geq 1$ for $j\in J$. Moreover

with probability at least $1-2^{-c\min\{sr,m\}}$.

since clearly $\|\Phi\|_{2}\leq\sqrt{n}$. Next, Lemma 22 and a union bound will ensure that $\|\Phi x^{\prime}\|_{2}\geq 1/(2\sqrt{s})$ for all $x^{\prime}\in\xi^{\prime}$ with the desired probability. ∎

Then with probability at least $1-e^{-cs}$ for some constant $c>0$, $\Phi$ satisfies

For the vectors $x\in\xi_{0}$, apply Corollary 23 with $x=x^{\prime},r=m/K^{2}$ (after rescaling by $n^{-K}$). Since $csr>cm>\log|\xi|\geq\log|\xi_{0}|$, (8.68) holds and by Eq. (8.69), we ensure that $\|\Phi x\|_{2}>n^{-K}/(4\sqrt{s})$ for all $x\in\xi_{0}$.

Let $\mathfrak{f}_{S}\subset B_{X_{S}}$ be a finite subset such that

Then with probability at least $1-e^{-cs}$ for some constant $c>0$, $\Phi|_{\mathcal{M}}$ is bi-Lipschitz, and more specifically

We treat separately the pairs $x,y\in\mathcal{M}$ which are at a “large” and “small” distance from each other. Fix $\varepsilon_{1}>0$ and $\varepsilon_{2}>\varepsilon_{1}$ to be specified later. Let $A_{\varepsilon_{1}}\subset\mathcal{M}$ be an $\varepsilon_{1}$-net for $\mathcal{M}$. By Eq. (8.74) and Eq. (A.6), we can assume that

Assume that $x,y\in\mathcal{M}$, $\|x-y\|_{2}>\varepsilon_{2}$. Take $x_{1},y_{1}\in A_{\varepsilon_{1}}$ s.t. $\|x-x_{1}\|_{2}<\varepsilon_{1}$, $\|y-y_{1}\|_{2}<\varepsilon_{1}$. Since $\Phi$ is linear

Therefore, if $x,y\in\mathcal{M}$, $\|x-y\|_{2}>\varepsilon_{2}$

choosing $\varepsilon_{2}=5\sqrt{n}e^{c(\log n)^{2}}\varepsilon_{1}$. This takes care of large distances.

In order to deal with small distances, we first ensure that

since $\varepsilon_{1}<n^{-1/2}e^{-c(\log n)^{2}}/2$. Thus $\Phi$ satisfies (8.80).

By Eq. (8.82) and using $\|\Phi\|\leq\sqrt{n}$,

Thus we may take $\log(1/\varepsilon_{1}),\log(1/\varepsilon_{2})\simeq(\log n)^{2}$ and condition (8.78) will hold for

Let $\mathcal{M}$ be as above and $m,s$ satisfy (8.76). Assume moreover that $m,s$ satisfy the appropriate conditions to ensure that

for all unit tangent vectors $v$ of $\mathcal{M}$. Then with probability at least $1-e^{-cs}$ for some constant $c>0$, $\Phi$ preserves geodesic distances up to factor $1+\varepsilon$.

By (8.84), $(1-\varepsilon)|\gamma|<|\Phi(\gamma)|<(1+\varepsilon)|\gamma|$ for any $C^{1}$-curve $\gamma$ in $\mathcal{M}$. Let $\rho_{\mathcal{M}}$ refer to the geodesic distance in $\mathcal{M}$. Clearly

from the above. We need to show the reverse inequality. Let $\gamma_{1}$ be a $C^{1}$-curve in $\Phi(\mathcal{M})$ joining $\Phi(x),\Phi(y)$ such that $\rho_{\Phi(\mathcal{M})}(\Phi(x),\Phi(y))=|\gamma_{1}|$. Since $\Phi$ satisfies (8.77), $\Phi|_{\mathcal{M}}:\mathcal{M}\rightarrow\Phi(\mathcal{M})$ is bi-Lipschitz and hence a diffeomorphism (since $\Phi$ is also smooth). It follows that $\gamma=\Phi^{-1}\gamma_{1}$ is a $C^{1}$-curve joining $x$ and $y$ and

Discussion

We have provided a general theorem which captures sparse dimensionality reduction in Euclidean space and qualitatively unifies much of what we know in specific applications. There is still much room though for quantitative improvement. We here list some known quantitative shortcomings of our bounds and discuss some avenues for improvement in future work.

First, our dependence on $1/\varepsilon$ in $s$ in all our theorems is, up to logarithmic factors, quadratic. Meanwhile the works show that the correct dependence in the case of small $m$ should be linear. Part of the reason for this discrepancy may be our use of the chaining result of . Specifically, chaining is a technique that in general converts tail bounds into bounds on the expected supremum of stochastic processes (see for details). Perhaps one could generalize the tail bound of to give a broad understanding of the decay behavior for the error random variable in the SJLT as a function of $s,m$ then feed such a quantity into a chaining argument to improve our use of .

Another place where we lost logarithmic factors is in our use of the duality of entropy numbers [21, Proposition 4] in Eq. (5.4). It is believed that in general if $K,D$ are symmetric convex bodies and $\mathcal{N}(K,D)$ is the number of translations of $D$ needed to cover $K$ then

for some universal constant $a>0$. This is known as Pietsch’s duality conjecture [81, p. 38], and unfortunately resolving it has been a challenging open problem in convex geometry for over 40 years.

Finally, note that the SJLT $\Phi$ considered in this work is a randomly signed adjacency matrix of a random bipartite graph with $m$ vertices in the left bipartition, $n$ in the right, and with all right vertices having equal degree $s$. Sasha Sodin has asked in personal communication whether taking a random signing of the adjacency matrix of a random biregular graph (degree $s$ on the right and degree $ns/m$ on the left) can yield improved bounds on $s,m$ for some $T$ of interest. We leave this as an interesting open question.