Sparsity and non-Euclidean embeddings

DOI10.1007/S11856-013-0014-YzbMATH Open1286.46015arXiv1107.0992OpenAlexW1997039324MaRDI QIDQ375782FDOQ375782

Omer Friedland, Olivier Guédon

Publication date: 31 October 2013

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

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$.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07)

Cites Work

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

Cited In (2)

• Optimally sparse representations of cartoon-like cylindrical data
• Title not available (Why is that?)

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)