Sparsity and non-Euclidean embeddings

We present a relation between sparsity and non-Euclidean isomorphic embeddings. We introduce a general restricted isomorphism property and show how it enables to construct embeddings of ${\mathrm{\ell }}_p^n$, $p>0$, into various type of Banach or quasi-Banach spaces. In particular, for $0<r<p<2$ with $r\le 1$, we construct a family of operators that embed ${\mathrm{\ell }}_p^n$ into ${\mathrm{\ell }}_r^{(1+\eta )n}$, with optimal polynomial bounds in $\eta >0$.