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 one to construct embeddings of ~? _p ~n, _p > 0, into various types of Banach or quasi-Banach spaces. In particular, for 0 < r < p < 2 with r ≤ 1, we construct a family of operators that embed ~? _p ~n into l_r ~((1+n)n), with sharp polynomial bounds in η > 0.