betaFeedback

WorksComputer Science

Optimal Injectivity of the SparseStack

Abstract

An Oblivious Subspace Injection (OSI) is a random sketching matrix that reliably preserves the minimum singular value of any fixed subspace with high constant probability, requiring only a one-sided spectral lower bound without controlling upper singular values. While classical Oblivious Subspace Embeddings (OSEs) fundamentally require row sparsity Ω(log⁡r)Ω(\log r) at linear sketch dimension k=O(r)k = O(r), we show that one-sided injectivity permits strictly sparser sketches, establishing matching (up to log⁡log⁡r\log\log r factors) upper and lower bounds of Θ~(log⁡r)\tildeΘ(\sqrt{\log r}). First, we prove that the SparseStack sketch achieves constant injectivity at linear dimension k=Θ(r)k = Θ(r) with row sparsity only ζ=O(log⁡r)ζ= O(\sqrt{\log r}), well below the Θ(log⁡r)Θ(\log r) barrier where standard operator-norm concentration fails. Second, we establish a matching lower bound: any isotropic random sketching matrix satisfying a mild row-overlap condition requires row sparsity ζ=Ω(log⁡r/log⁡log⁡r)ζ= Ω(\sqrt{\log r / \log \log r}) to achieve linear-dimension injectivity, confirming that the log⁡r\sqrt{\log r} scale is fundamental. To bypass the lack of an operator-norm upper bound when ζ=O(log⁡r)ζ= O(\sqrt{\log r}), we decouple the sketch into two independent halves and introduce three techniques: (i) a uniform lower bound for flat vectors via randomized rounding, controlling discretization error using solely the Frobenius norm; (ii) a Gaussian truncation and minimax duality argument showing that all non-flat vectors escaping injectivity in the first half concentrate on a single universal coordinate subset I⊆[n]I \subseteq [n] of size O(r/ζ)O(r/ζ), bypassing union bounds over supports; and (iii) a two-tier coordinate isolation analysis in the second half that suppresses collisions to e−Ω(ζ2)≪1/re^{-Ω(ζ^2)} \ll 1/r, reliably preserving these heavy coordinates.

AI Disclosure Statement. The authors utilized the colosseum harness [22] on top of Gemini 4 throughout the mathematical development of this work. Specifically, the vast majority of the technical proofs and mathematical derivations in this manuscript were generated and drafted by the model. The human authors independently established several key structural lemmas, improved the exposition, and carefully verified all mathematical steps. Furthermore, this work is accompanied by a fully functional, machine-checked formal proof in Lean 4. The human authors audited the formalization to confirm that all definitions and theorem statements faithfully and accurately encode the intended mathematical results. The machine-checked formal proof in Lean 4 is publicly available at GitHub repository. The authors take full responsibility for the accuracy, rigor, and conclusions of this work.

Introduction

Sketching is the workhorse of randomized linear algebra: we replace a large matrix by a small random image of it and do the expensive work on the image [32, 18, 40, 26]. To sketch a matrix A∈Rn×dA \in\mathbb{R}^{n \times d}, we draw a tall random matrix Ω∈Rn×k\Omega\in\mathbb{R}^{n \times k} and form the product ΩTA\Omega^{\mathsf{T}} A. To measure the cost of a sketching method, we need to consider two aspects. First is the embedding dimension kk, which controls the size of (and therefore cost of working on) the image; when the problem is governed by an rr-dimensional subspace, the natural goal is k=O(r)k = O(r). Second, we need to account for the cost of computing ΩTA\Omega^{\mathsf{T}} A. Indeed, if Ω\Omega is a dense Gaussian matrix, then computing ΩTA\Omega^{\mathsf{T}} A can easily become the computation bottleneck.

To resolve this, a very popular approach is to use sparse random matrices [11, 25, 21 MDM+23, 7]. If Ω\Omega has at most ζ\zeta nonzeros per row, then we can form the sketch ΩTA\Omega^{\mathsf{T}} A in O(ζnnz⁡(A))O(\zeta\operatorname{nnz}(A)) time. We call ζ\zeta the row sparsity of Ω\Omega. This paper studies a single question: how sparse can the test matrix be when k=O(r)k = O(r) while still being reliable for numerical algorithms?

Embeddings and Injections

Classically, randomized numerical linear algebra (RNLA) methods have used the Oblivious Subspace Embedding (OSE) condition to characterize when a sketching matrix is reliable [32, 40, 34, 26, 6]. We say that Ω∈Rn×k\Omega\in\mathbb{R}^{n \times k} is an OSE if, for every matrix Q∈Rn×rQ \in\mathbb{R}^{n \times r} with orthonormal columns, we have

(1−ε)Ir⪯QTΩΩTQ⪯(1+ε)Ir(1-\varepsilon)I_r \preceq Q^{\mathsf{T}}\Omega\Omega^{\mathsf{T}}Q \preceq(1+\varepsilon)I_r

with high probability. Equivalently, the OSE guarantee ensures that vectors in the range of QQ are neither stretched nor squished by large amount. A long line of work has shown that sparse sketching matrices with embedding dimension k=O(r)k = O(r) and constant dilation ε=1/2\varepsilon= 1/2 must have row sparsity ζ=Ω(log⁡r)\zeta= \Omega(\log r), and that this rate is achieved by the SparseStack matrix (see below) [8, 28, 5, 3, 4, 17].

While the OSE definition is natural, and is guaranteed to hold for many sketching matrices, it is often also overkill. Several works in RNLA show that many downstream algorithms, like methods for low-rank approximation [18, 40, 27, 26, 6] and least-squares regression [30, 13, 6]—do not actually require a two-sided guarantee. Instead, it suffices for the sketch to satisfy a one-sided lower bound:

QTΩΩTQ⪰αIr,or equivalently∥ΩTQx∥2≥α∥x∥2for all x∈Rr,(1)Q^{\mathsf{T}}\Omega\Omega^{\mathsf{T}}Q \succeq\alpha I_r, \qquad\text{or equivalently} \qquad\lVert\Omega^{\mathsf{T}}Qx\rVert^2 \geq\alpha\lVert x\rVert^2 \quad\text{for all } x \in\mathbb{R}^r, \tag*{(1)}

where α>0\alpha> 0 is called the injectivity parameter, all subject the normalization criteria E[ΩΩT]=I\mathbb{E}[\Omega\Omega^{\mathsf{T}}] = I. While this weaker criteria was known or folklore in specific contexts, its systematic study was initiated by Camaño, Epperly, Meyer, and Tropp [6], who introduced the term Oblivious Subspace Injection (OSI). It will be helpful to think of the OSI condition in terms of spectra. Indeed, equation (1) holds if and only if

σmin⁡(ΩTQ)2≥α\sigma_{\min}(\Omega^{\mathsf{T}}Q)^2 \geq\alpha

with high constant probability.

The central question we want to understand is, at linear sketch dimension k=Θ(r)k = \Theta(r), how small can we make the row sparsity ζ\zeta while maintaining constant injectivity α\alpha. Most specifically, can a sparse matrix be an OSI with sparsity ζ=o(log⁡r)\zeta= o(\log r), proving that the OSEs formalism is unable to fully justify when sparse matrices are reliable numerical tools? We answer this in the affirmative.

The SparseStack sketch. To minimize both sketching time and storage, a popular family of structured random matrices in RNLA is CountSketch [11, 2, 37] and its multi-block generalization, SparseStack [38, 28, 25, 29, 8, 6]. Throughout this paper, a SparseStack sketch matrix Ωζ,b∈Rn×k\Omega_{\zeta,b} \in\mathbb{R}^{n \times k} has n≥rn \ge r rows, row sparsity ζ\zeta, and total embedding dimension k=ζb=Θ(r)≪nk = \zeta b = \Theta(r) \ll n.

We define these matrices directly in terms of independent Rademacher signs and sparse coordinate selections. Let e1,…,eb∈Rbe_1,\ldots,e_b \in\mathbb{R}^{b} denote the standard basis vectors. A CountSketch matrix Φ∈Rn×b\Phi\in\mathbb{R}^{n \times b} has rows given by

Φ=[ϱ1es1T⋮ϱnesnT]∈Rn×b,whereϱi∼Rademacher⁡ i.i.d.;si∼Uniform⁡{1,…,b} i.i.d.(2)\Phi= \begin{bmatrix} \varrho_1 e_{s_1}^{\mathsf{T}}\\ \vdots\\ \varrho_n e_{s_n}^{\mathsf{T}} \end{bmatrix} \in\mathbb{R}^{n \times b}, \qquad \text{where}\qquad \varrho_i \sim\operatorname{Rademacher}\ \mathrm{i.i.d.}; \qquad s_i \sim\operatorname{Uniform}\{1,\ldots,b\}\ \mathrm{i.i.d.} \tag*{(2)}

That is, each row of Φ\Phi contains a single non-zero entry ϱi∈{−1,1}\varrho_i \in\{-1,1\} placed at an independent, uniformly chosen column index si∈[b]s_i \in[b].

A SparseStack matrix Ωζ,b∈Rn×k\Omega_{\zeta,b} \in\mathbb{R}^{n \times k} with row sparsity ζ\zeta, block size bb, and dimension k=ζbk = \zeta b horizontally concatenates ζ\zeta independent CountSketch matrices Φ1,…,Φζ∼Φ\Phi_1,\ldots,\Phi_\zeta\sim\Phi, scaled by ζ−1/2\zeta^{-1/2}.

Ωζ,b:=1ζ[Φ1 ⋯ Φζ]=1ζ[ϱ1,1es1,1T⋯ϱ1,ζes1,ζTϱ2,1es2,1T⋯ϱ2,ζes2,ζT⋮⋱⋮ϱn,1esn,1T⋯ϱn,ζesn,ζT]∈Rn×k,(3)\Omega_{\zeta,b} := \frac{1}{\sqrt{\zeta}}\left[\Phi_1\ \cdots\ \Phi_\zeta\right] = \frac{1}{\sqrt{\zeta}} \begin{bmatrix} \varrho_{1,1}e_{s_{1,1}}^{\mathsf{T}} & \cdots& \varrho_{1,\zeta}e_{s_{1,\zeta}}^{\mathsf{T}}\\ \varrho_{2,1}e_{s_{2,1}}^{\mathsf{T}} & \cdots& \varrho_{2,\zeta}e_{s_{2,\zeta}}^{\mathsf{T}}\\ \vdots& \ddots& \vdots\\ \varrho_{n,1}e_{s_{n,1}}^{\mathsf{T}} & \cdots& \varrho_{n,\zeta}e_{s_{n,\zeta}}^{\mathsf{T}} \end{bmatrix} \in\mathbb{R}^{n \times k}, \tag*{(3)}

where {ϱit}\{\varrho_{it}\} are i.i.d. Rademacher random variables and {sit}\{s_{it}\} are i.i.d. uniform random indices on [b][b]. By construction, every row of Ωζ,b\Omega_{\zeta,b} has exactly ζ\zeta non-zero entries of magnitude ζ−1/2\zeta^{-1/2} and unit Euclidean norm. Since distinct rows have mean-zero inner products, Ωζ,b\Omega_{\zeta,b} is isotropic in expectation.

Proof methods for OSEs and the Θ(log⁡r)\Theta(\log r) barrier. In the two-sided (1±ε)(1 \pm\varepsilon)-OSE setting, SparseStack is the block-independent model within the OSNAP framework of Nelson and Nguyen [28] and Cohen [8]. Recent work by Heidary [17] established that dimension k=Θ(r/ε2)k = \Theta(r/\varepsilon^2) and row sparsity ζ=Θ((log⁡r)/ε)\zeta= \Theta((\log r)/\varepsilon) are both sufficient and optimal for a two-sided (1±ε)(1 \pm\varepsilon)-embedding.

Existing methods establish injectivity by viewing the SparseStack as an average of independent CountSketch blocks, giving

ATA=QTΩζ,bΩζ,bTQ=1ζ∑t=1ζQTΦtΦtTQ.(4)A^{\mathsf{T}}A = Q^{\mathsf{T}}\Omega_{\zeta,b}\Omega_{\zeta,b}^{\mathsf{T}}Q = \frac{1}{\zeta}\sum_{t=1}^{\zeta} Q^{\mathsf{T}}\Phi_t\Phi_t^{\mathsf{T}}Q. \tag*{(4)}

In particular, using matrix comparison theorems, Tropp [35] proved that row sparsity ζ=Θ(log⁡r)\zeta= \Theta(\log r) ensures σmin⁡(A)2≥Ω(1)\sigma_{\min}(A)^2 \ge\Omega(1) at linear sketch dimension k=Θ(r)k = \Theta(r). The question of whether constant injectivity is achievable with row sparsity strictly below Θ(log⁡r)\Theta(\log r) was posed by Camaño et al. [6] and has remained open.

Techniques that analyze ATAA^{\mathsf{T}}A directly as a sum of independent blocks hit a conceptual barrier at row sparsity Θ(log⁡r)\Theta(\log r). Below this threshold, the largest singular value σmax⁡(A)\sigma_{\max}(A) is no longer bounded by O(1)O(1) with high probability. It is easy to see this via a coupon-collector argument: hashing $r basis coordinates into b=Θ(r/ζ)b = \Theta(r/\zeta) buckets in a block inevitably creates overloaded buckets where Θ(log⁡(r/ζ)/log⁡log⁡(r/ζ2))=ω(ζ)\Theta(\log(r/\zeta)/\log\log(r/\zeta^{2})) = \omega(\zeta) coordinates collide, and a unit vector aligned with those colliding coordinates has its entries add up to give ∥Ωζ,bQx∥=ω(1)\lVert\Omega_{\zeta,b}Qx\rVert= \omega(1).

Nonetheless, it has been experimentally shown that SparseStacks, as well as other sparse sketching matrices, are OSIs with favorable values of α\alpha even when ζ=4\zeta= 4 and k=2rk = 2r [MDM+23, CEMT25]. Motivated by these questions, Camaño et al. [6] conjectured that constant row sparsity ζ=O(1)\zeta= O(1) might suffice for an OSI at linear dimension k=Θ(r)k = \Theta(r). However, Huang, Rudelson, and Tikhomirov [19] recently refuted this conjecture, showing that constant row sparsity fails for any OSI distribution. This leaves open the central question: What is the true optimal sparsity for an Oblivious Subspace Injection? Does injectivity inherently require Θ(log⁡r)\Theta(\log r) sparsity as in the two-sided OSE case, or does the relaxation to one-sided injectivity permit a strictly sparser sketch?

Main Results

In this paper, we resolve this question by establishing matching (up to log⁡log⁡r\log\log r factors) upper and lower bounds on the row sparsity of OSI at linear embedding dimension, showing that the optimal threshold is Θ~(log⁡r)\widetilde{\Theta}(\sqrt{\log r}).

Our first main result is an upper bound proving that SparseStack achieves constant injectivity at linear embedding dimension with row sparsity only O(log⁡r)O(\sqrt{\log r}), well below the Θ(log⁡r)\Theta(\log r) barrier of two-sided embeddings.

References

  1. [1][Car79] Yair Caro. New results on the independence number. Technical report, Tel-Aviv University, 1979.
  2. [2][CCFC02] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International colloquium on automata, languages, and programming, pages 693–703. Springer, 2002.
  3. [3][CDD24] Shabarish Chenakkod, Michał Dereziński, and Xiaoyu Dong. Optimal oblivious subspace embeddings with near-optimal sparsity. arXiv preprint arXiv:2411.08773, 2024.arxiv.org/abs/2411.08773
  4. [4][CDD26] Shabarish Chenakkod, Michał Dereziński, and Xiaoyu Dong. 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. SIAM, 2026.arxiv.org/abs/2508.14234
  5. [5][CDDR24] Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, and Mark Rudelson. Optimal embedding dimension for sparse subspace embeddings. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1106–1117, 2024.DOI
  6. [6][CEMT25] Chris Camaño, Ethan N. Epperly, Raphael A. Meyer, and Joel A. Tropp. Faster linear algebra algorithms with structured random matrices. arXiv preprint arXiv:2508.21189, 2025.arxiv.org/abs/2508.21189
  7. [7][CNR+26] Tyler Chen, Pradeep Niroula, Archan Ray, Pragna Subrahmanya, Marco Pistoia, and Niraj Kumar. Gpu-parallelizable randomized sketch-and-preconditioning for linear regression using sparse sign sketches. In 2026 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 411–420. IEEE, 2026.arxiv.org/abs/2506.03070
  8. [8][Coh16] Michael B. Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 278–287, 2016.
  9. [9][CTV06] Kevin P Costello, Terence Tao, and Van Vu. Random symmetric matrices are almost surely nonsingular. 2006.DOI
  10. [10][CV10] Kevin P Costello and Van Vu. On the rank of random sparse matrices. Combinatorics, Probability and Computing, 19(3):321–342, 2010.arxiv.org/abs/0711.2696
  11. [11][CW13] Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pages 81–90, 2013.
  12. [12][DGM24] Patrick DeMichele, Margalit Glasgow, and Alexander Moreira. On the rank, kernel, and core of sparse random graphs. Random Structures & Algorithms, 65(4):719–793, 2024.arxiv.org/abs/2105.11718
  13. [13]Petros Drineas, Michael W Mahoney, Shan Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. Numerische mathematik, 117(2):219–249, 2011.
  14. [14]Ding-Zhu Du and Panos M Pardalos. Minimax and applications, volume 4. Springer Science & Business Media, 1995.
  15. [15]Margalit Glasgow, Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney. The exact rank of sparse random graphs. arXiv preprint arXiv:2303.05435, 1(3):4, 2025.arxiv.org/abs/2303.05435
  16. [16]Philip Hall. On representatives of subsets. Journal of the London Mathematical Society, s1-10(1):26–30, 1935.
  17. [17]Diar Heidary. SparseStack is an optimal oblivious subspace embedding. arXiv preprint arXiv:2609.02978v2, 2026.arxiv.org/abs/2609.02978
  18. [18]Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217–288, 2011.arxiv.org/abs/0909.4061
  19. [19]Han Huang, Mark Rudelson, and Konstantin Tikhomirov. Well-invertible column subsets of sparse matrices are rare. arXiv preprint arXiv:2607.05384, 2026.arxiv.org/abs/2607.05384
  20. [20]Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney. Sharp invertibility of random bernoulli matrices. arXiv preprint arXiv:2010.06553, 2020.arxiv.org/abs/2010.06553
  21. [21]Daniel M. Kane and Jelani Nelson. Sparser Johnson–Lindenstrauss transforms. Journal of the ACM, 61(1):4:1–4:23, 2014.
  22. [22]Honghao Lin, David P. Woodruff, Yuan Deng, Jieming Mao, Song Zuo, and Vahab Mirrokni. Stellar colosseum: A many-agent harness for long-horizon research in mathematics and theoretical computer science, 2026.arxiv.org/abs/2609.15983
  23. [23]Colin McDiarmid. On the method of bounded differences. In Surveys in Combinatorics, 1989, volume 141 of London Mathematical Society Lecture Note Series, pages 148–188. Cambridge University Press, 1989.DOI
  24. [25]Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 91–100, 2013.arxiv.org/abs/1210.3135
  25. [26]Per-Gunnar Martinsson and Joel A. Tropp. Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica, 29:403–572, 2020.DOI
  26. [27]Cameron Musco and David P Woodruff. Sublinear time low-rank approximation of positive semidefinite matrices. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 672–683. IEEE, 2017.arxiv.org/abs/1704.03371
  27. [28]Jelani Nelson and Huy L. Nguyễn. 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, 2013.arxiv.org/abs/1211.1002
  28. [29]Ninh Pham and Rasmus Pagh. Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 239–247, 2013.DOI
  29. [30]Vladimir Rokhlin and Mark Tygert. A fast randomized algorithm for overdetermined linear least-squares regression. Proceedings of the National Academy of Sciences, 105(36):13212–13217, 2008.
  30. [31]Mark Rudelson and Roman Vershynin. The smallest singular value of a random rectangular matrix, 2009. URL https://arxiv.org/abs/0802.3956, 5(2).
  31. [32]Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 143–152, 2006.DOI
  32. [33]Konstantin Tikhomirov. Singularity of random bernoulli matrices. Annals of Mathematics, 191(2):593–634, 2020.arxiv.org/abs/1812.09016
  33. [34]Joel A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1–2):1–230, 2015.arxiv.org/abs/1501.01571
  34. [35]Joel A. Tropp. Comparison theorems for the minimum eigenvalue of a random positive-semidefinite matrix. Communications of the American Mathematical Society, 6:844–895, 2026. arXiv:2501.16578v1.DOI
  35. [36]Paul Turán. Eine Extremalaufgabe aus der Graphentheorie. Matematikai és Fizikai Lapok, 48:436–452, 1941.
  36. [37]Mikkel Thorup and Yin Zhang. Tabulation based 4-universal hashing with applications to second moment estimation. In SODA, volume 4, pages 615–624, 2004.DOI
  37. [38]Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning, pages 1113–1120, 2009.arxiv.org/abs/0902.2206
  38. [39]Victor K. Wei. A lower bound on the stability number of a graph. Technical report, Bell Laboratories Technical Memorandum 81-11217-9, 1981.
  39. [40]David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1–2):1–157, 2014.DOI

Paper details

vlnc:W_9v8sw8q9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Computer Science

colosseum harness

View statement
Looking for related papers…
Contents