{"id":"arxiv/2609.02978","url":"https://arxiv.org/abs/2609.02978","tags":["cs.DS","math.NA"],"score":0,"title":"SparseStack Is an Optimal Oblivious Subspace Embedding","domain":"cs.DS","source":"arxiv","authors":["Diar Heidary"],"reviews":0,"subject":"cs.DS","summary":"We prove that fully independent SparseStack achieves the oblivious subspace embedding parameters conjectured by Nelson and Nguyen (FOCS 2013): $m=O((d+\\log(1/δ))/\\varepsilon^2)$ rows and $s=O(\\log(d/δ)/\\varepsilon)$ nonzero entries per column for distortion $\\varepsilon$ and failure probability $δ$ 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}