Anup B. Rao

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