## Abstract

For a family of interpolation norms ‖ · ‖ _{1} _{,} _{2} _{,} _{s} on R^{n}, we provide a distribution over random matrices Φ _{s}∈ R^{m} ^{×} ^{n} parametrized by sparsity level s such that for a fixed set X of K points in R^{n}, if m≥ Cslog (K) then with high probability, 12‖x‖1,2,s≤‖Φs(x)‖1≤2‖x‖1,2,s for all x∈ X. Several existing results in the literature roughly reduce to special cases of this result at different values of s: For s = n, ‖ x‖ _{1} _{,} _{2} _{,} _{n}≡ ‖ x‖ _{1} and we recover that dimension reducing linear maps can preserve the ℓ_{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, ‖ x‖ _{1 , 2 , 1}≡ ‖ x‖ _{2}, and we recover an ℓ_{2}/ℓ_{1} variant of the Johnson–Lindenstrauss Lemma for Gaussian random matrices. Finally, if x is s- sparse, then ‖ x‖ _{1} _{,} _{2} _{,} _{s}= ‖ x‖ _{1} and we recover that s-sparse vectors in ℓ1n embed into ℓ1O(slog(n)) via sparse random matrix constructions.

Original language | English |
---|---|

Pages (from-to) | 209-231 |

Number of pages | 23 |

Journal | Results in Mathematics |

Volume | 70 |

Issue number | 1-2 |

DOIs | |

State | Published - 1 Sep 2016 |

## Keywords

- 15B52
- 46B09
- 46B70