## Abstract

Let Φ∈Rm×n be a sparse Johnson–Lindenstrauss transform (Kane and Nelson in J ACM 61(1):4, 2014) with s non-zeroes per column. For a subset T of the unit sphere, ε∈(0,1/2) given, we study settings for m, s required to ensure

EΦsupx∈T∣∣∥Φx∥22−1∣∣<ε,

i.e. so that Φ preserves the norm of every x∈T simultaneously and multiplicatively up to 1+ε. We introduce a new complexity parameter, which depends on the geometry of T, and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon’s theorem, which was concerned with a dense Φ having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson–Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson–Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.

EΦsupx∈T∣∣∥Φx∥22−1∣∣<ε,

i.e. so that Φ preserves the norm of every x∈T simultaneously and multiplicatively up to 1+ε. We introduce a new complexity parameter, which depends on the geometry of T, and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon’s theorem, which was concerned with a dense Φ having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson–Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson–Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.

Original language | English |
---|---|

Pages (from-to) | 1009-1088 |

Journal | Geometric and Functional Analysis |

Volume | 25 |

Issue number | 4 |

DOIs | |

Publication status | Published - Jul 2015 |

Externally published | Yes |

## Keywords

- Unify Theory
- Random Projection
- Restricted Isometry Property
- Numerical Linear Algebra
- Lindenstrauss Lemma