TOWARD A UNIFIED THEORY OF SPARSE DIMENSIONALITY REDUCTION IN EUCLIDEAN SPACE
📜 Abstract
Let Φ ∈ R^{m×n} be a sparse Johnson-Lindenstrauss transform [KN14] 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_Φ sup_{x∈T} |‖Φx‖²₂ − 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.
✨ Summary
The paper develops a general theory for when a sparse Johnson–Lindenstrauss transform preserves the Euclidean norm uniformly over an arbitrary subset T of the unit sphere. Its central contribution is a geometry-sensitive complexity parameter, κ(T), that supplements the Gaussian mean width. The resulting theorem gives sufficient conditions on the embedding dimension m and column sparsity s, together with a constraint involving κ(T), for uniform norm preservation.
The analysis models the sparse transform through a random coordinate-induced seminorm and controls the resulting supremum of a second-order Rademacher chaos using generic chaining, covering-number duality, Maurey-type approximations, dual Sudakov bounds, and concentration inequalities. This framework separates the Euclidean complexity of T from its coordinate-sensitive structure, which is necessary because sparse transforms are basis-dependent and therefore are not invariant under arbitrary orthogonal changes of coordinates.
Applications include:
- Finite sets: recovery of sparse Johnson–Lindenstrauss bounds, including improvements for vectors with bounded ℓ∞ norm.
- Linear subspaces: sparse oblivious subspace embeddings, with sparsity further controlled by the subspace coherence or leverage scores.
- Sparse and model-based vectors: restricted-isometry results for ordinary sparsity, dictionaries, unions of subspaces, and block-sparse models.
- Constrained least squares: guarantees for sketched least-squares, group Lasso, and Lasso problems. The sparsity requirement can depend on the largest entry of the design matrix rather than only on column norms.
- Manifolds: conditions under which sparse maps preserve tangent-vector norms, curve lengths, manifold embeddings, and geodesic distances. The paper also gives a construction showing that strong coordinate incoherence is necessary for substantially sparse embeddings in some manifold settings.
The paper explicitly identifies quantitative limitations: its sparsity bounds generally lose logarithmic factors and have quadratic rather than optimal linear dependence on ε^{-1}; the authors relate these losses to entropy-duality estimates, dual Sudakov bounds, and chaining arguments.
Bibliographic and citation records confirm subsequent dissemination in both the STOC 2015 proceedings and the 2015 Geometric and Functional Analysis journal publication. Later work cites the paper in research on random matrices acting on sets, restricted-isometry properties, and concentration inequalities for non-Gaussian or log-concave-tailed chaoses. (research-portal.uu.nl) The paper’s documented impact is primarily theoretical: it provided a common framework connecting sparse Johnson–Lindenstrauss embeddings, subspace embeddings, compressed sensing, manifold embeddings, and randomized numerical linear algebra. The sources checked did not establish a specific direct industry deployment.