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/δ))/ε2) rows and s=O(log(d/δ)/ε) nonzero entries per column for distortion ε 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 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 ℓ≥1 occupied sites sharing the external factor ℝd by d+ℓ−1 rather than dℓ, 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.
Related
- Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
- Bias-Corrected Subspace Intersection: Minimax-Optimal Shared Subspace Estimation in Multi-View Data
- A Near-Optimal Lower Bound for ℓp-Subspace Embeddings, 1≤ p<2
- Optimal Personalized Subspace Learning for Multi-view Tensor Observations
- New binary optimal LCD codes using heuristic embedding
BibTeX
@misc{heidary2026sparsestack,
title = {{SparseStack Is an Optimal Oblivious Subspace Embedding}},
author = {Diar Heidary},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02978},
eprint = {2609.02978},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02978},
}
RIS
TY - UNPB
TI - SparseStack Is an Optimal Oblivious Subspace Embedding
AU - Diar Heidary
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.02978
UR - https://arxiv.org/abs/2609.02978
AB - We prove that fully independent SparseStack achieves the oblivious subspace embedding parameters conjectured by Nelson and Nguyen (FOCS 2013): m=O((d+log(1/δ))/ε^2) rows and s=O(log(d/δ)/ε) nonzero entries per column for distortion ε 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 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 ℓ≥1 occupied sites sharing the external factor ℝ^d by d+ℓ−1 rather than dℓ, 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.
ER -