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 \ge d\) and \(\varepsilon \ge d^{-O(1)}\), there is a random \(\tilde{O}(d/\varepsilon^2) \times n\) matrix \(\Pi\) with \(\tilde{O}(\log(d)/\varepsilon)\) non-zeros per column such that for any \(A \in \mathbb{R}^{n \times d}\), with high probability, \((1 - \varepsilon)\|Ax\| \le \|\Pi Ax\| \le (1 + \varepsilon)\|Ax\|\) for all \(x \in \mathbb{R}^d\), where \(\tilde{O}(\cdot)\) hides only sub-polylogarithmic factors in \(d\). Our result in particular implies a new fastest sub-current matrix multiplication time reduction of size \(\tilde{O}(d/\varepsilon^2)\) for a broad class of \(n \times d\) linear regression tasks.