# Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors

arXiv: https://arxiv.org/abs/2508.14234 · HTML: https://mlsanity.com/paper/2508.14234/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2025.

## Built on by (most cited first, 2 of 2)

- [Adaptive randomized pivoting and volume sampling](https://mlsanity.com/paper/2510.02513/) (2025)
- [The Advantages of Fresh Sketching for Ridge Regression](https://mlsanity.com/paper/2609.38565/) (2026)

## Abstract (arXiv)

We give a proof of the conjecture of Nelson and Nguyen [FOCS 2013] on the optimal dimension and sparsity of oblivious subspace embeddings, up to sub-polylogarithmic factors: For any n≥ d and ε≥ d-O(1), there is a random tilde O(d/ε2)× n matrix Pi with tilde O(log(d)/ε) non-zeros per column such that for any A∈ℝn× d, with high probability, (1-ε)|Ax|≤|Pi Ax|≤(1+ε)|Ax| for all x∈ℝd, where tilde O(·) hides only sub-polylogarithmic factors in d. Our result in particular implies a new fastest sub-current matrix multiplication time reduction of size tilde O(d/ε2) for a broad class of n× d linear regression tasks. A key novelty in our analysis is a matrix concentration technique we call iterative decoupling, which we use to fine-tune the higher-order trace moment bounds attainable via existing random matrix universality tools [Brailovskaya and van Handel, GAFA 2024].