Sparsity and non-Euclidean embeddings

Abstract

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 ${\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 ${\ell }_p^n$ into ${\ell }_r^{(1+\eta )n}$, with optimal polynomial bounds in $\eta >0$.