Optimal Injectivity of the SparseStack

arXiv:2611.12867 · cs.DS · Submitted 2026-11-09 · Read on arXiv

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

Related papers