SparseStack Is an Optimal Oblivious Subspace Embedding

Abstract

We prove that fully independent SparseStack achieves the oblivious subspace embedding parameters conjectured by Nelson and Nguyen (FOCS 2013): $m=O((d+\log(1/\delta))/\varepsilon^2)$ rows and $s=O(\log(d/\delta)/\varepsilon)$ nonzero entries per column for distortion $\varepsilon$ and failure probability $\delta$ on any fixed $d$-dimensional subspace, with explicit constants. The proof turns random-matrix concentration into a problem in finite-dimensional linear algebra. A coupling first reduces the moment estimates to a model with independent finite-valued entries. We represent these variables by multiplication operators, so their matrix moments become exact matrix elements of a deterministic operator on a finite tensor product. The central estimate bounds the contribution of $\ell\ge1$ occupied sites sharing the external factor $\mathbb{R}^d$ by $d+\ell-1$ rather than $d\ell$, yielding additive dependence on the dimension and the moment order. This approach controls both spectral edges without Gaussian comparison. The main theorem has been formally verified in Lean 4.