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.

An oblivious subspace embedding is a random m× n matrix Π such that, for any d-dimensional subspace, with high probability Π preserves the norms of all vectors in that subspace within a 1±ε factor. In this work, we give an oblivious subspace embedding with the optimal dimension m = Θ(d/ε²) that has a near-optimal sparsity of Õ(1/ε) non-zero entries per column of Π. This is the first result to nearly match the conjecture of Nelson and Nguyen [FOCS 2013] in terms of the best sparsity attainable by an optimal oblivious subspace embedding, improving on a prior bound of Õ(1/ε⁶) non-zeros per column [Chenakkod et al., STOC 2024]. We further extend our approach to the non-oblivious setting, proposing a new family of Leverage Score Sparsified embeddings with Independent Columns, which yield faster runtimes for matrix approximation and regression tasks. In our analysis, we develop a new method which uses a decoupling argument together with the cumulant method for bounding the edge universality error of isotropic random matrices. To achieve near-optimal sparsity, we combine this general-purpose approach with new trace inequalities that leverage the specific structure of our subspace embedding construction.

A random m× n matrix S is an oblivious subspace embedding (OSE) with parameters є>0, δ∈(0,1/3) and d≤ m≤ n, if for any d-dimensional subspace W⊆ Rn, P( ∀x∈ W (1+є)−1||x||≤ ||Sx||≤ (1+є)||x|| )≥ 1−δ. It is known that the embedding dimension of an OSE must satisfy m≥ d, and for any θ > 0, a Gaussian embedding matrix with m≥ (1+θ) d is an OSE with є = Oθ(1). However, such optimal embedding dimension is not known for other embeddings. Of particular interest are sparse OSEs, having s≪ m non-zeros per column (Clarkson and Woodruff, STOC 2013), with applications to problems such as least squares regression and low-rank approximation.