SparseStack Is an Optimal Oblivious Subspace Embedding
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.02978
curl -X POST /api/v1/records/arxiv/2609.02978/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.02978/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'