Toward a unified theory of sparse dimensionality reduction in Euclidean space

Abstract

Let $\Phi \in {\mathbb{R}}^{m\times n}$ be a sparse Johnson-Lindenstrauss transform [KN14] with $s$ non-zeroes per column. For a subset $T$ of the unit sphere, $\epsilon \in (0,1/2)$ given, we study settings for $m,s$ required to ensure $${\mathbb{E}}_{\Phi }\underset{x\in T}{\sup }\left|\Vert \Phi x{\Vert }_2^2-1\right|<\epsilon ,$$ i.e. so that $\Phi$ preserves the norm of every $x\in T$ simultaneously and multiplicatively up to $1+\epsilon$. 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 $\Phi$ 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.

References in corpus (5)

• A Technique for Extracting Highly Precise Photometry for the Two-Wheeled Kepler Mission
• Fast approximation of matrix coherence and statistical leverage
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• On Model-Based RIP-1 Matrices

Cited by in corpus (4)

• Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets
• Compressed Subspace Matching on the Continuum
• Fast Generalized Matrix Regression with Applications in Machine Learning
• Tighter bound of Sketched Generalized Matrix Approximation