The Gelfand widths of ${\ell }_p$-balls for $0<p\le 1$

Abstract

We provide sharp lower and upper bounds for the Gelfand widths of ${\ell }_p$-balls in the $N$-dimensional ${\ell }_q^N$-space for $0<p\le 1$ and $p<q\le 2$. Such estimates are highly relevant to the novel theory of compressive sensing, and our proofs rely on methods from this area.

arXiv comment15 pages

Cited by in corpus (8)

• The restricted isometry property for time-frequency structured random matrices
• Restricted Isometries for Partial Random Circulant Matrices
• Stability of low-rank matrix recovery and its connections to Banach space geometry
• Gelfand and Kolmogorov numbers of Sobolev embeddings of weighted function spaces II
• Gelfand and Kolmogorov numbers of Sobolev embeddings of weighted function spaces
• Widths of embeddings in weighted function spaces
• Metric entropy, n-widths, and sampling of functions on manifolds
• Widths of embeddings of 2-microlocal Besov spaces