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 Õ(d/ϵ 2 ) × n matrix Π with Õ(log(d)/ϵ) non-zeros per column such that for any A ∈ R n×d , with high probability, (1 -ϵ)∥Ax∥ ≤ ∥ΠAx∥ ≤ (1 + ϵ)∥Ax∥ for all x ∈ R d , where Õ(•) hides only sub-polylogarithmic factors in d. Our result in particular implies a new fastest sub-current matrix multiplication time reduction of size Õ(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].