Research map / Learning theory and algorithms / Matrix and tensor methods
Sparse Dimensionality Reduction Revisited
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Revisits sparse Johnson-Lindenstrauss embeddings, exploiting d << n to give a sparser CountSketch-based (Kane-Nelson) embedding, a matching lower bound when d is small, and improved sparsity for oblivious subspace embeddings at optimal dimension.
Problem
Sparsity of embedding matrices for Johnson-Lindenstrauss and oblivious subspace embeddings: the best known upper bound O(eps^-1 lg n) and the Nelson-Nguyen lower bound only apply when d >= n, which is unrealistic in many applications where d << n.
Approach
Split each vector into heavy and light entries; bound the number of possible heavy supports via the dimension d (or subspace dimension k) rather than n, and control light entries with small l_inf/l_2 ratio results (Jagadeesan), yielding sparsity depending on lg d instead of lg n. A new lower bound uses a harder instance (sums of lg n/lg d standard basis vectors) that works when d << n.
Key results
- Upper bound s = O(eps^-1 (lg n/lg(1/eps) + lg^{2/3} n lg^{1/3} d)) for sparse JL when d << n, improving on O(eps^-1 lg n).
- Lower bound s = Omega(eps^-1 lg n/lg(m/lg n)) holds for d << n, matching the first term of the upper bound; tight when lg n >= lg d * lg^3(1/eps).
- Subspace embedding with optimal m = O(k/eps^2) and sparsity O(eps^-1 (k/lg(1/eps) + k^{2/3} lg^{1/3} k)), beating black-box SparseJL's O(k/eps).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use input dimension d in the SparseJL sparsity analysis | Kane-Nelson SparseJL · JL embedding (n vectors in R^d) | column sparsity s: O(ε^{-1} lg n) -> O(ε^{-1}(lg n/lg(1/ε) + lg^{2/3} n lg^{1/3} d)) | Helped |
| Construct a hard input set that applies when d << n | Sparse JL lower-bound analysis · JL embedding (n vectors in R^d) | column sparsity s lower bound: Ω(ε^{-1} lg n/lg(1/ε)) for n=d -> Ω(lg n/(ε lg(m/lg n))) | Helped |
| Use a dimension-aware sparsity analysis while keeping optimal embedding dimension | SparseJL for oblivious subspace embeddings · k-dimensional oblivious subspace embedding | column sparsity s: O(k/ε) -> O(ε^{-1}(k/lg(1/ε) + k^{2/3} lg^{1/3} k)) | Helped |
Limitations
- Improvements are asymptotic and arguably small
- Subspace sparsity remains far from conjectured optimal O(lg k/eps)
- Upper bound holds with probability 1-O(1/d) and only for O(eps)-JL after rescaling
Experimental setup
Baselines: Kane and Nelson sparse JL Nelson and Nguyen lower bound SparseJL black-box subspace embedding Cohen subspace embedding Clarkson-Woodruff
Builds on: Kane and Nelson sparse JL Nelson and Nguyen lower bound Jagadeesan small l_inf embedding result Cohen subspace embedding
Closest papers by meaning
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.92)
- Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.89)
- Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry (NeurIPS 2025 · similarity 0.86)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.86)
- A general kernel framework for non-CND distance measures using $|\mathcal{D}|$-dimensional sparse landmark embeddings (NeurIPS 2026 · similarity 0.86)
- Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.