Sharp (m, s) tradeoffs for the sparse Johnson-Lindenstrauss transform on general sets: epsilon-dependence of the column sparsity, logarithmic losses, and biregular random models

The sparse Johnson-Lindenstrauss transform (SJLT) is an $m\times n$ random matrix whose columns each hold exactly $s$ nonzero entries, equal to random signs $\pm 1/\sqrt{s}$ placed at uniformly random rows, so that the image of a vector $x$ costs only $O(s\|x\|_0)$ time to compute. Bourgain, Dirksen, and Nelson (Geometric and Functional Analysis, 2015) proved a sparse analogue of Gordon's comparison theorem: for every set $T$ on the Euclidean unit sphere, the SJLT preserves all norms on $T$ within $1+\varepsilon$ in expectation once $m \gtrsim (\log m)^3(\log n)^5(g^2(T)+1)/\varepsilon^2$ and $s \gtrsim (\log m)^6(\log n)^4/\varepsilon^2$, subject to a side condition on a complexity parameter $\kappa(T)$, where $g(T)$ is the Gaussian mean width of $T$. The paper's discussion section explicitly flags three quantitative defects as open problems: (1) the sparsity $s$ depends quadratically on $1/\varepsilon$ (up to logarithmic factors) in every theorem of the paper, whereas the settled special cases - finite point sets, and single linear subspaces - achieve linear dependence; (2) polylogarithmic losses in both $m$ and $s$ enter through the duality of entropy numbers (tied to a covering-number duality conjecture open since 1972) and through the passage from dual Sudakov minoration to the $\gamma_2$ functional; (3) whether alternative sparse random models, notably randomly signed adjacency matrices of random biregular bipartite graphs (a question posed to the authors by Sasha Sodin), yield better $(m,s)$ tradeoffs for structured $T$. The subspace special case of (1) has recently been essentially resolved - Chenakkod-Derezinski-Dong achieved the optimal dimension $m = O(d/\varepsilon^2)$ with sparsity $s = \tilde{O}(1/\varepsilon)$ (arXiv 2024, ICALP 2025), and their strengthened version (SODA 2026) proves the 2013 conjecture of Nelson-Nguyen up to sub-polylogarithmic factors - but the question for general $T$, the removal of the logarithmic losses, and the biregular-model question all remain open.

Background

The Johnson-Lindenstrauss lemma (JL lemma) states that any set of $n$ points in Euclidean space admits a linear map into $m = O(\varepsilon^{-2}\log n)$ dimensions that preserves all pairwise distances up to a factor $1\pm\varepsilon$; this target dimension is known to be optimal. Random matrices yield such maps with high probability, but a dense $m\times n$ random matrix costs $\Omega(mn)$ time to apply, which can dominate the cost of the computation being accelerated. If instead the embedding matrix has at most $s$ nonzeros per column, the image of a vector $x$ can be computed in $O(s\|x\|_0)$ time, where $\|x\|_0$ counts the nonzero coordinates of $x$; for high-dimensional and sparse data, the column sparsity $s$ is therefore the parameter that governs embedding cost.

The standard sparse model is the sparse Johnson-Lindenstrauss transform (SJLT): an $m\times n$ matrix with independent columns, each having exactly $s$ nonzero entries placed at uniformly random rows and filled with independent random signs $\pm 1/\sqrt{s}$. Equivalently, it is a randomly signed adjacency matrix of a random bipartite graph with $n$ right vertices of degree $s$ and $m$ left vertices of unconstrained degree. Kane and Nelson proved that for a finite set $T$ the SJLT preserves all norms on $T$ within $1\pm\varepsilon$ with $s = O(\varepsilon^{-1}\log|T|)$ and $m = O(\varepsilon^{-2}\log|T|)$, and Nelson and Nguyen constructed point sets for which any linear dimensionality-reducing map requires sparsity $s = \Omega(\varepsilon^{-1}\log n/\log(1/\varepsilon))$: linear dependence of $s$ on $1/\varepsilon$ is essentially optimal for finite sets.

Applications, however, ask for embeddings of infinite sets. Taking $T$ to be the unit sphere of an unknown $d$-dimensional subspace $E\subset\mathbb{R}^n$ yields oblivious subspace embeddings (OSEs) - random matrices that embed every $d$-dimensional subspace - which underpin fast algorithms for least-squares regression, low-rank approximation, and the Lasso, a widely used constrained least-squares regression estimator whose statistical analysis is governed by a tangent cone of the constraint set, itself a set $T$ of this type. Taking $T$ to be the unit $k$-sparse vectors, $T = \{x : \|x\|_2 = 1,\ \|x\|_0 \le k\}$, yields the restricted isometry property (RIP), the condition on compressed-sensing measurement matrices that guarantees sparse-signal recovery. Model-based compressed sensing (unions of subspaces) and manifold learning supply further structured sets. For a dense matrix $\Phi$ with i.i.d. standard Gaussian entries, Gordon's comparison theorem - a Gaussian-process result comparing expected suprema of Gaussian processes via their mean widths - gives the complete answer for arbitrary $T \subseteq \mathbb{S}^{n-1}$ (the unit sphere of $\mathbb{R}^n$): $\mathbb{E}_\Phi \sup_{x\in T} |\|\Phi x\|_2^2 - 1| < \varepsilon$ whenever $m \gtrsim (g^2(T)+1)/\varepsilon^2$, where $g(T) = \mathbb{E}\sup_{x\in T}\langle g,x\rangle$ for a standard Gaussian vector $g$ is the Gaussian mean width of $T$, the standard geometric complexity parameter of a set. Gordon's theorem implies the JL lemma (since $g^2(T) \le \log|T|$ up to constants for finite $T$) and fixes the benchmark dimension $m \approx g^2(T)/\varepsilon^2$. Throughout, $\gtrsim$ suppresses absolute constant factors.

Bourgain, Dirksen, and Nelson asked the sparse analogue of Gordon's question - the main question of their paper: what must $m$ and $s$ satisfy, as functions of the geometry of an arbitrary $T \subseteq \mathbb{S}^{n-1}$, for the SJLT to satisfy the same expected-supremum condition? Their main theorem, still the only general result, states that it suffices that

$m \gtrsim (\log m)^3(\log n)^5\,\frac{g^2(T)+1}{\varepsilon^2}, \qquad s \gtrsim (\log m)^6(\log n)^4\,\frac{1}{\varepsilon^2},$

together with the side condition $(\log m)^2(\log n)^{5/2}\,\kappa(T) < \varepsilon$, where $\kappa(T) = \kappa_{s,m}(T)$ is a complexity parameter they introduce: an expected supremum over $T$ of a normalized second-order process built from independent Gaussian and Bernoulli random variables, capturing how the sparsity pattern interacts with the coordinate structure of $T$. This sparse Gordon theorem qualitatively unifies the previously known special cases and gives the first nontrivial sparse bounds for model-based compressed sensing, manifold embeddings, and constrained least squares such as the Lasso.

The theorem, however, loses quantitative factors that the authors themselves identified in the paper's discussion section. First, in every theorem of the paper the sparsity $s$ carries a quadratic dependence on $1/\varepsilon$ up to logarithmic factors, while Kane-Nelson's finite-set result and Nelson-Nguyen's OSNAP subspace construction (OSNAP, an acronym for oblivious sparse norm-approximating projection, is a block-sampled variant of the SJLT in which the rows are partitioned into $s$ blocks and each column places one nonzero at a random row of each block; it achieves $s = \mathrm{polylog}(d)/\varepsilon$ at $m = \tilde{O}(d/\varepsilon^2)$, where $\tilde{O}$ suppresses polylogarithmic factors) show the correct dependence is linear when the embedding dimension $m$ is of optimal order. The quadratic factor enters through the chaining step: chaining is the generic technique that converts tail bounds for a random process into bounds on its expected supremum, and Bourgain-Dirksen-Nelson feed in a moment bound for suprema of second-order Rademacher chaos processes (a chaos process is a quadratic form $\sum_{ij} A_{ij} X_i X_j$ in independent random variables) due to Krahmer-Mendelson-Rauhut; the authors suggest that sharper tail bounds for the SJLT error as a function of $(s,m)$, fed into a chaining argument, might recover the linear dependence. Second, both $m$ and $s$ lose polylogarithmic factors at two identified places: (i) through the duality of entropy numbers - for symmetric convex bodies $K, D$ with $N(K,D)$ the least number of translates of $D$ needed to cover $K$ and $K^\circ$ the polar body of $K$, the proof needs covering bounds for polars, and the best general tool, due to Bourgain-Pajor-Szarek-Tomczak-Jaegermann, holds only up to logarithmic factors, the exact statement being the conjecture that $N(D^\circ, aK^\circ) \asymp N(K,D) \asymp N(D^\circ, a^{-1}K^\circ)$ for a universal constant $a$, posed in 1972 (often called Pietsch's duality conjecture; entropy numbers measure how well an operator between Banach spaces can be approximated by finite-rank operators), a long-standing open problem in convex geometry whose central Hilbert-space case was settled by Artstein-Milman-Szarek; and (ii) through passing from dual Sudakov minoration - an entropy lower bound for Gaussian processes in terms of the expected norm $\mathbb{E}\|P_E g\|_X$ of a Gaussian projection under an arbitrary norm $\|\cdot\|_X$ - to the $\gamma_2$ functional, a weighted sum of covering numbers that exactly characterizes expected suprema of Gaussian processes via the majorizing-measures theorem; this passage is known to be lossless only when the underlying metric is Euclidean. Third, the SJLT regularizes degrees only on the right side of the bipartite graph; Sasha Sodin asked the authors (in personal communication documented in the paper) whether a random signing of the adjacency matrix of a random biregular graph - right degree $s$, left degree $ns/m$ - could yield improved bounds on $s, m$ for some $T$ of interest, and they left this as an open question.

Problem Statement

The problem is to determine the quantitatively sharp relationship between the embedding dimension $m$ and the column sparsity $s$ that the sparse Johnson-Lindenstrauss transform (SJLT) - an $m\times n$ matrix whose independent columns each have exactly $s$ nonzero entries, each a random sign $\pm 1/\sqrt{s}$ at a uniformly random row - must satisfy, as a function of the geometry of an arbitrary target set $T \subseteq \mathbb{S}^{n-1}$, in order that

$\mathbb{E}_\Phi \sup_{x \in T} \left| \|\Phi x\|_2^2 - 1 \right| < \varepsilon.$

Bourgain, Dirksen, and Nelson proved sufficiency of $m \gtrsim (\log m)^3(\log n)^5 (g^2(T)+1)/\varepsilon^2$ and $s \gtrsim (\log m)^6(\log n)^4/\varepsilon^2$ (here and throughout, $\gtrsim$ suppresses absolute constant factors and $\tilde{O}$ suppresses polylogarithmic factors), subject to $(\log m)^2(\log n)^{5/2}\kappa(T) < \varepsilon$, where $g(T)$ is the Gaussian mean width and $\kappa(T)$ their complexity parameter. Three quantitative defects of this theorem, explicitly identified by the authors, define the open core; the common objective is a sharp sparse Gordon theorem with no unnecessary losses:

(a) Epsilon-dependence of the sparsity, for general $T$. All bounds of the source paper make $s$ quadratic in $1/\varepsilon$ up to logarithmic factors, while the settled special cases (finite $T$ by Kane-Nelson; a single $d$-dimensional subspace by Nelson-Nguyen's OSNAP and its successors, most recently Chenakkod-Derezinski-Dong, whose 2026 version resolves the Nelson-Nguyen sparsity conjecture for this case up to sub-polylogarithmic factors) achieve linear dependence. Determine whether $s$ with linear $1/\varepsilon$-dependence suffices for general $T$ at (near-)optimal dimension $m = \tilde{O}(g^2(T)/\varepsilon^2)$, or exhibit sets $T$ for which quadratic dependence of $s$ on $1/\varepsilon$ is necessary for any column-sparse random construction.

(b) Logarithmic losses. Remove the polylogarithmic factors lost in $m$ and $s$: (i) through the duality of entropy numbers, where only the logarithmic-factor version of Bourgain-Pajor-Szarek-Tomczak-Jaegermann is available and the exact statement is the duality conjecture for entropy numbers, open since 1972 (Hilbert-space case settled by Artstein-Milman-Szarek); and (ii) through the passage from dual Sudakov minoration to the $\gamma_2$ functional, a loss avoidable only in the Euclidean case.

(c) Alternative sparse random models. The SJLT is the signed adjacency matrix of a random bipartite graph regular on the right only. Determine whether a random signing of the adjacency matrix of a random biregular graph (right degree $s$, left degree $ns/m$) - or another explicitly specified sparse random model - achieves strictly better $(m,s)$ tradeoffs for some classes of $T$ than the best known SJLT bounds for the same classes, or show that no such improvement is possible in the model.

The three parts serve one objective: a complete, quantitatively sharp characterization of which pairs $(m,s)$ suffice as a function of the geometry of $T$. Such a characterization is tight up to constants for general $T$ with the correct $\varepsilon$-dependence, and settles whether alternative sparse models improve the tradeoff.

References

1. Jean Bourgain, Sjoerd Dirksen, and Jelani Nelson (2015). Toward a unified theory of sparse dimensionality reduction in Euclidean space. Geometric and Functional Analysis 25(4):1009-1088. DOI: 10.1007/s00039-015-0332-9, https://doi.org/10.1007/s00039-015-0332-9. Full text also as arXiv:1311.2542, https://arxiv.org/abs/1311.2542.
2. Daniel M. Kane and Jelani Nelson (2014). Sparser Johnson-Lindenstrauss transforms. Journal of the ACM 61(1):1-23, Article 4. DOI: 10.1145/2559902, https://doi.org/10.1145/2559902.
3. Jelani Nelson and Huy L. Nguyen (2013). OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 117-126. DOI: 10.1109/FOCS.2013.21, https://doi.org/10.1109/FOCS.2013.21. Full text also as arXiv:1211.1002, https://arxiv.org/abs/1211.1002.
4. Jelani Nelson and Huy L. Nguyen (2013). Sparsity lower bounds for dimensionality-reducing maps. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pages 101-110. DOI: 10.1145/2488608.2488622, https://doi.org/10.1145/2488608.2488622. Full text also as arXiv:1211.0995, https://arxiv.org/abs/1211.0995.
5. Yehoram Gordon (1988). On Milman's inequality and random subspaces which escape through a mesh in R^n. In Geometric Aspects of Functional Analysis (Israel Seminar 1986-87), Lecture Notes in Mathematics 1317, pages 84-106. DOI: 10.1007/BFb0081737, https://doi.org/10.1007/bfb0081737.
6. Shiri Artstein-Avidan, Vitali Milman, and Stanisław Szarek (2004). Duality of metric entropy. Annals of Mathematics 159(3):1313-1328. DOI: 10.4007/annals.2004.159.1313, https://doi.org/10.4007/annals.2004.159.1313. Preprint arXiv:math/0407236, https://arxiv.org/abs/math/0407236 (the preprint lists the first author under the earlier name S. Artstein).
7. Jean Bourgain, Alain Pajor, Stanislaw J. Szarek, and Nicole Tomczak-Jaegermann (1989). On the duality problem for entropy numbers of operators. In Geometric Aspects of Functional Analysis (Israel Seminar 1987-88), Lecture Notes in Mathematics 1376, pages 50-63. DOI: 10.1007/BFb0090048, https://doi.org/10.1007/bfb0090048.
8. Felix Krahmer, Shahar Mendelson, and Holger Rauhut (2014). Suprema of chaos processes and the restricted isometry property. Communications on Pure and Applied Mathematics 67(11):1877-1904. DOI: 10.1002/cpa.21504, https://doi.org/10.1002/cpa.21504.
9. Michael B. Cohen (2016). Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 278-287. DOI: 10.1137/1.9781611974331.ch21, https://doi.org/10.1137/1.9781611974331.ch21.
10. Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, and Chris Schwiegelshohn (2024). Sparse Dimensionality Reduction Revisited. In Proceedings of the 41st International Conference on Machine Learning (ICML), PMLR 235:18454-18469. https://proceedings.mlr.press/v235/hogsgaard24a.html. Preprint arXiv:2302.06165 (first posted 2023), https://arxiv.org/abs/2302.06165.
11. Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, and Mark Rudelson (2024). Optimal embedding dimension for sparse subspace embeddings. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1106-1117. DOI: 10.1145/3618260.3649762, https://doi.org/10.1145/3618260.3649762. Full text also as arXiv:2311.10680, https://arxiv.org/abs/2311.10680.
12. Shabarish Chenakkod, Michał Dereziński, and Xiaoyu Dong (2026). Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4501-4559. DOI: 10.1137/1.9781611978971.163, https://doi.org/10.1137/1.9781611978971.163. Preprint arXiv:2508.14234, https://arxiv.org/abs/2508.14234. An earlier version of this line of work appeared as Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity, In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), Leibniz International Proceedings in Informatics (LIPIcs) 55:1-55:20. DOI: 10.4230/LIPIcs.ICALP.2025.55, https://doi.org/10.4230/LIPIcs.ICALP.2025.55; preprint arXiv:2411.08773, https://arxiv.org/abs/2411.08773 (version 2 revised April 2025).
13. Tatiana Brailovskaya and Ramon van Handel (2024). Universality and sharp matrix concentration inequalities. Geometric and Functional Analysis 34(6):1734-1838. DOI: 10.1007/s00039-024-00692-9, https://doi.org/10.1007/s00039-024-00692-9. Preprint arXiv:2201.05142 (first posted 2022), https://arxiv.org/abs/2201.05142.
14. Shahar Mendelson (2022). Column randomization and almost-isometric embeddings. Information and Inference 12(1):1-25. DOI: 10.1093/imaiai/iaab028, https://doi.org/10.1093/imaiai/iaab028. Preprint arXiv:2103.05237, https://arxiv.org/abs/2103.05237.
15. Yaniv Plan and Roman Vershynin (2025). Random matrices acting on sets: independent columns. Electronic Journal of Probability 30 (2025). DOI: 10.1214/25-ejp1404, https://doi.org/10.1214/25-ejp1404. Preprint arXiv:2502.16827, https://arxiv.org/abs/2502.16827.
16. Kwassi Joseph Dzahini and Stefan M. Wild (2025). A class of sparse Johnson-Lindenstrauss transforms and analysis of their extreme singular values. SIAM Journal on Matrix Analysis and Applications 46(1):416-438. DOI: 10.1137/23m1605661, https://doi.org/10.1137/23m1605661. Preprint arXiv:2212.14858 (first posted 2022), https://arxiv.org/abs/2212.14858.
17. Edem Boahen, March T. Boedihardjo, Rafael Chiclana, and Mark Iwen (2025). On extended concentration inequalities for fast JL embeddings of infinite sets. In 2025 International Conference on Sampling Theory and Applications (SampTA), pages 1-5. DOI: 10.1109/SampTA64769.2025.11133506, https://doi.org/10.1109/SampTA64769.2025.11133506. Preprint arXiv:2501.14010, https://arxiv.org/abs/2501.14010.
18. Yi Li and Mingmou Liu (2026). Sparsity-dimension trade-offs for oblivious subspace embeddings. Proceedings of the ACM on Management of Data 4(2):1-25. DOI: 10.1145/3801912, https://doi.org/10.1145/3801912.