Sparsity and non-Euclidean embeddings

DOI10.1007/S11856-013-0014-YMaRDI QIDQ375782zbMATH OpenOpenAlexFDO

Authors Omer Friedland, Olivier Guédon

Publication date 31 October 2013

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.0992

zbMATH Keywords

sparsityembeddings of \(\ell^n_p\)restricted isomorphism property

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07)

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 $el{l}_p^n$, $p>0$, into various type of Banach or quasi-Banach spaces. In particular, for $0<r<p<2$ with $rle1$, we construct a family of operators that embed $el{l}_p^n$ into $el{l}_r^{(1+eta)n}$, with optimal polynomial bounds in $eta>0$.

Recommendations

• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Sparser Johnson-Lindenstrauss transforms
• Random embedding of \({\ell_p^n}\) into \({\ell_r^N}\)
• The restricted isometry property meets nonlinear approximation with redundant frames
• Sparsity lower bounds for dimensionality reducing maps

Cites work

• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 3359145 (Why is no real title available?)
• Compressed sensing
• Convergence to a stable distribution via order statistics
• Decoding by Linear Programming
• Embedding \(\ell^ n_ p\) into \(r\)-Banach spaces, \(0<r\leq p<2\)
• Embedding \(l_ p^ m\) into \(l_ 1^ n\)
• Gelfand numbers of operators with values in a Hilbert space
• Isomorphic embedding of \(\ell_p^n\), \(1<p<2\), into \(\ell_1^{(1+\varepsilon)n}\)
• On the Dimension of the l n p -Subspaces of Banach Spaces, for 1 p < 2
• Polynomial bounds for large Bernoulli sections of _1N
• Random embedding of \({\ell_p^n}\) into \({\ell_r^N}\)
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Sparse recovery with pre-Gaussian random matrices
• Special orthogonal splittings of \(L_1^{2k}\)
• Stable signal recovery from incomplete and inaccurate measurements
• Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach
• Tail estimates and a random embedding of \(\ell^n_p\) into \(l_r^{(1+ \varepsilon)n}\), \(0<r<p<2\)
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Very tight embeddings of subspaces of \(L_p\), \(1 \leq p < 2\), into \(\ell^n_p\)

Cited in

(2)

• scientific article; zbMATH DE number 6154260 (Why is no real title available?)
• Optimally sparse representations of cartoon-like cylindrical data

This page was built for publication: Sparsity and non-Euclidean embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q375782)