A unified framework for linear dimensionality reduction in L1

Abstract

For a family of interpolation norms $\Vert \cdot {\Vert }_{1,2,s}$ on ${\mathbb{R}}^n$, we provide a distribution over random matrices $\hat{I}{¦}_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\ge Cs\log (K)$ then with high probability, $\frac{1}{2}\Vert x{\Vert }_{1,2,s}\le \Vert \hat{I}{¦}_s(x){\Vert }_1\le 2\Vert x{\Vert }_{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$, $\Vert x{\Vert }_{1,2,n}\equiv \Vert x{\Vert }_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$, $\Vert x{\Vert }_{1,2,1}\equiv \Vert x{\Vert }_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 $\Vert x{\Vert }_{1,2,s}=\Vert x{\Vert }_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.

18 pages, 1 figure