# Exponentially Improved Dimensionality Reduction for ℓ1: Subspace Embeddings and Independence Testing

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2021.

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

- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Single Pass Entrywise-Transformed Low Rank Approximation](https://mlsanity.com/paper/2107.07889/) (2021)
- [ℓp-Regression in the Arbitrary Partition Model of Communication](https://mlsanity.com/paper/2307.05117/) (2023)
- [Coresets for Multiple ℓp Regression](https://mlsanity.com/paper/2406.02432/) (2024)

## Abstract (arXiv)

Despite many applications, dimensionality reduction in the ℓ1-norm is much less understood than in the Euclidean norm. We give two new oblivious dimensionality reduction techniques for the ℓ1-norm which improve exponentially over prior ones: 1. We design a distribution over random matrices S ∈ ℝr × n, where r = 2tilde O(d/(varepsilon δ)), such that given any matrix A ∈ ℝn × d, with probability at least 1-δ, simultaneously for all x, |SAx|1 = (1 ± varepsilon)|Ax|1. Note that S is linear, does not depend on A, and maps ℓ1 into ℓ1. Our distribution provides an exponential improvement on the previous best known map of Wang and Woodruff (SODA, 2019), which required r = 2^2Omega(d), even for constant varepsilon and δ. Our bound is optimal, up to a polynomial factor in the exponent, given a known 2√ d lower bound for constant varepsilon and δ. 2. We design a distribution over matrices S ∈ ℝk × n, where k = 2O(q2)(varepsilon-1 q log d)O(q), such that given any q-mode tensor A ∈ (ℝd)otimes q, one can estimate the entrywise ℓ1-norm |A|1 from S(A). Moreover, S = S1 otimes S2 otimes cdots otimes Sq and so given vectors u1, ldots, uq ∈ ℝd, one can compute S(u1 otimes u2 otimes cdots otimes uq) in time 2O(q2)(varepsilon-1 q log d)O(q), which is much faster than the dq time required to form u1 otimes u2 otimes cdots otimes uq. Our linear map gives a streaming algorithm for independence testing using space 2O(q2)(varepsilon-1 q log d)O(q), improving the previous doubly exponential (varepsilon-1 log d)^qO(q) space bound of Braverman and Ostrovsky (STOC, 2010).