A unified framework for linear dimensionality reduction in L1 (Q310869)

For a family of interpolation norms \(\|\cdot \|_{1,2,s}\) on \(\mathbb{R}^n\) the authors 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\) holds: if \(m\geq Cs\log (K)\) then with high probability \(\frac12 \| x\|_{1,2,s}\leq \|\Phi_s(x)\|_1\leq 2\| x\|_{1,2,s}\) for all \(x\in X\). In this way, they manage to recove some existiong results in the literature (for \(s=n\), \(s=1\)).