Optimal Injectivity of the SparseStack
cs.DS
Submitted: 2026-11-09
Updated: 2026-11-09
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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…
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 Ω(r) at linear sketch dimension k = O(r), we show that one-sided injectivity permits strictly sparser sketches, establishing matching (up to r factors) upper and lower bounds of Θ(sqrt r). First, we prove that the SparseStack sketch achieves constant injectivity at linear dimension k = Θ(r) with row sparsity only ζ= O(sqrt r), well below the Θ(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 ζ= Ω(sqrt r / r) to achieve linear-dimension injectivity, confirming that the sqrt r scale is fundamental. To bypass the lack of an operator-norm upper bound when ζ= O(sqrt 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] of size 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) much less than 1/r, reliably preserving these heavy coordinates.
Sources
- Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
- Faster Linear Algebra Algorithms with Structured Random Matrices
- The Exact Rank of Sparse Random Graphs
- Well-invertible column subsets of sparse matrices are rare
- Sharp invertibility of random Bernoulli matrices
- Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software
- Comparison theorems for the minimum eigenvalue of a random positive-semidefinite matrix
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time