The Gelfand widths of lp-balls for 0p<=1

Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich

Abstract

We provide sharp lower and upper bounds for the Gelfand widths of ℓ p -balls in the N -dimensional ℓ q N -space for 0 < p ≤ 1 and p < q ≤ 2 . Such estimates are highly relevant to the novel theory of compressive sensing, and our proofs rely on methods from this area.
BibTeX
@article{foucart2010gelfand,
  author = {Simon Foucart and Alain Pajor and Holger Rauhut and Tino Ullrich},
  title = {{The Gelfand widths of lp-balls for 0p<=1}},
  journal = {Journal of Complexity},
  year = {2010},
  doi = {10.1016/j.jco.2010.04.004},
}
Figure