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

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].