  For a family of interpolation norms $\| \cdot \|_{1,2,s}$ on $\mathbb{R}^n$,
we provide a distribution over random matrices $\Phi_s \in \mathbb{R}^{m \times
n}$ parametrized by sparsity level $s$ such that for a fixed set $X$ of $K$
points in $\mathbb{R}^n$, if $m \geq C s \log(K)$ then with high probability,
$\frac{1}{2} \| x \|_{1,2,s} \leq \| \Phi_s (x) \|_1 \leq 2 \| x\|_{1,2,s}$ for
all $x\in 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 $\ell_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 $\ell_2 / \ell_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 $\ell_1^n$ embed into $\ell_1^{\mathcal{O}(s
\log(n))}$ via sparse random matrix constructions.
