# Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity

arXiv: https://arxiv.org/abs/2411.08773 · HTML: https://mlsanity.com/paper/2411.08773/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 13 Nov 2024.

## Builds on (most cited first, 15 of 15)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [Lower bounds for oblivious subspace embeddings](https://mlsanity.com/paper/1308.3280/) (2013)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2211.09964/) (2022)
- [Hashing embeddings of optimal dimension, with applications to linear least squares](https://mlsanity.com/paper/2105.11815/) (2021)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs](https://mlsanity.com/paper/2206.10291/) (2022)
- [Lower Bounds for Sparse Oblivious Subspace Embeddings](https://mlsanity.com/paper/2112.10987/) (2021)

## Built on by (most cited first, 4 of 4)

- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation](https://mlsanity.com/paper/2605.09755/) (2026)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)
- [The Advantages of Fresh Sketching for Ridge Regression](https://mlsanity.com/paper/2609.38565/) (2026)

## Abstract (arXiv)

An oblivious subspace embedding is a random m× n matrix Pi such that, for any d-dimensional subspace, with high probability Pi 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=Theta(d/ε2) that has a near-optimal sparsity of tilde O(1/ε) non-zero entries per column of Pi. 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 tilde O(1/ε6) 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 traces inequalities that leverage the specific structure of our subspace embedding construction.