Oblivious subspace embeddings with optimal dimension and sparsity
The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration
Data Structures and Algorithms
Summary
In big data and machine learning, it's useful to reduce data size without losing important details. The paper solves a key math problem about embedding data with fewer dimensions while keeping distances almost the same. The authors prove a conjecture that shows how to do this efficiently with fewer resources. They used clever mathematical techniques and also employed an AI assistant to help with the proof and writing.
What this means in practice
- •For machine learning engineers: Reduce the size of data representations in training models while preserving accuracy with proven guarantees on embedding efficiency.
- •For data compression teams: Develop data compression methods that maintain key geometric properties with fewer computations and storage resources.
A theory result. No direct application yet.
Authors
Tung Mai, Anup Rao
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 < δ< 1$, there exists a distribution that gives an OSE with embedding dimension $O((d + \log(1/δ))/\varepsilon^2)$ and column sparsity $s = O(\log(d/δ)/\varepsilon)$, with failure probability at most $δ$. 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.