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

Abstract

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/\delta))/\varepsilon^2)$ and column sparsity $s = O(\log(d/\delta)/\varepsilon)$, 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.