# A unified framework for linear dimensionality reduction in L1

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 May 2014.

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

- [Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey](https://mlsanity.com/paper/2108.04172/) (2021)

## Abstract (arXiv)

For a family of interpolation norms | · |1,2,s on ℝn, we provide a distribution over random matrices Phis ∈ ℝm × n parametrized by sparsity level s such that for a fixed set X of K points in ℝn, if m ≥ C s log(K) then with high probability, frac12 | x |1,2,s ≤ | Phis (x) |1 ≤ 2 | x|1,2,s for all x∈ X. Several existing results in the literature reduce to special cases of this result at different values of s: for s=n, | x|1,2,n equiv | x |1 and we recover that dimension reducing linear maps can preserve the ℓ1-norm up to a distortion proportional to the dimension reduction factor, which is known to be the best possible such result. For s=1, |x |1,2,1 equiv | x |2, and we recover an ℓ2 / ℓ1 variant of the Johnson-Lindenstrauss Lemma for Gaussian random matrices. Finally, if x is s-sparse, then | x |1,2,s = | x |1 and we recover that s-sparse vectors in ℓ1n embed into ℓ1O(s log(n)) via sparse random matrix constructions.