# Tight Bounds for ℓp Oblivious Subspace Embeddings

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2018.

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

- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Non-PSD Matrix Sketching with Applications to Regression and Optimization](https://mlsanity.com/paper/2106.08544/) (2021)
- [ℓp-Regression in the Arbitrary Partition Model of Communication](https://mlsanity.com/paper/2307.05117/) (2023)

## Abstract (arXiv)

An ℓp oblivious subspace embedding is a distribution over r × n matrices Pi such that for any fixed n × d matrix A, PrPi[textrmfor all x,  |Ax|p ≤ |Pi Ax|p ≤ kappa |Ax|p] ≥ 9/10, where r is the dimension of the embedding, kappa is the distortion of the embedding, and for an n-dimensional vector y, |y|p is the ℓp-norm. Another important property is the sparsity of Pi, that is, the maximum number of non-zero entries per column, as this determines the running time of computing Pi · A. While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparisty, for the important case of 1 ≤ p < 2, much less was known. In this paper we obtain nearly optimal tradeoffs for ℓp oblivious subspace embeddings for every 1 ≤ p < 2. We show for every 1 ≤ p < 2, any oblivious subspace embedding with dimension r has distortion kappa = Omega left(frac1left(frac1dright)1 / p · log2 / pr + left(fracrnright)1 / p - 1 / 2right). When r = poly(d) in applications, this gives a kappa = Omega(d1/plog-2/p d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 and the oblivious subspace embedding of Meng and Mahoney (STOC, 2013) for 1 < p < 2 are optimal up to poly(log(d)) factors. We also give sparse oblivious subspace embeddings for every 1 ≤ p < 2 which are optimal in dimension and distortion, up to poly(log d) factors. Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise ℓp low rank approximation. Our results give improved algorithms for these applications.