A unified framework for linear dimensionality reduction in L1

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.