The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration

An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every $0<\delta <1$, there exists a distribution that gives an OSE with embedding dimension $O((d+\log (1\mathrm{/}\delta ))\mathrm{/}{\epsilon }^2)$ and column sparsity $s=O(\log (d\mathrm{/}\delta )\mathrm{/}\epsilon )$, with failure probability at most $\delta$. We first bound the mean spectral error using a trace-moment argument and then upgrade this bound to the desired high-probability guarantee using concentration and resampling. ChatGPT-5.6-Pro was used in proving and writing the results of this manuscript.