A Unified Framework for Linear Dimensionality Reduction in L1

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}\| \varvec{x} \|_{1,2,s} \leq \| \Phi_s (\varvec{x}) \|_1 \leq 2 \| \varvec{x} \|_{1,2,s}}\) for all \({\varvec{x} \in X}\). Several existing results in the literature roughly reduce to special cases of this result at different values of s: For s = n, \({\| \varvec{x} \|_{1,2,n}\equiv \| \varvec{x} \|_{1}}\) and we recover that dimension reducing linear maps can preserve the ?₁-norm up to a distortion proportional to the dimension reduction factor, which is known to be the best possible such result. For s = 1, \({\| \varvec{x} \|_{1,2,1}\equiv \| \varvec{x} \|_{2}}\), and we recover an ?₂/?₁ variant of the Johnson–Lindenstrauss Lemma for Gaussian random matrices. Finally, if \({\varvec{x}}\) is s- sparse, then \({\| \varvec{x} \|_{1,2,s} = \| \varvec{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.