The Gelfand widths of $\ell_p$-balls for $0<p\leq 1$

Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich

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 \leq 1$ and $p < q \leq 2$. Such estimates are highly relevant to the novel theory of compressive sensing, and our proofs rely on methods from this area.

Introduction

In the field of compressive sensing, a central objective is the reconstruction of high-dimensional signals from a limited number of linear measurements. To understand the fundamental limits of this process, mathematicians employ the concept of Gelfand widths. For a given set $K$ in a normed (or quasi-normed) space $X$, the $m$-th Gelfand width $d^m(K, X)$ quantifies the smallest possible worst-case error achievable using any $m$ linear measurements.

Specifically, for $0 < p \leq 1$, the $\ell_p$-ball $B_p^N$ serves as a critical model for sparse and compressible signals. While David Donoho provided initial estimates for these widths in 2006, a significant mathematical gap remained. His lower bound proof relied on "Carl's theorem," a tool from functional analysis established for standard Banach spaces ($p \geq 1$). However, for $p < 1$, the $\ell_p$ spaces are quasi-Banach spaces where the triangle inequality is replaced by a $p$-convexity condition, rendering traditional tools inapplicable. This work rigorously closes that gap, establishing sharp asymptotic behavior for these widths.

Methodology: Compressive Sensing as a Geometric Tool

Traditionally, bounds on Gelfand widths are derived using classical approximation theory—such as Kolmogorov widths, duality arguments, or entropy numbers. Because these methods often fail in the quasi-normed regime, this research inverts the standard relationship: it utilizes the algorithmic theory of compressive sensing to prove fundamental theorems in pure geometry.

The Lower Bound

The authors establish the lower bound through a proof by contradiction centered on the $\ell_p$-null space property (NSP). The NSP is a necessary and sufficient condition for a measurement matrix to allow exact recovery of sparse vectors via $\ell_p$-minimization. By employing a volumetric argument on quotient spaces, the authors demonstrate that if the Gelfand width were smaller than the proposed bound, it would imply the existence of a measurement scheme capable of recovering sparse vectors with fewer measurements than is information-theoretically possible.

The Upper Bound

The upper bound is established using the Restricted Isometry Property (RIP). The authors show that random Gaussian matrices satisfy the RIP with high probability. By demonstrating that standard $\ell_p$-minimization algorithms achieve optimal worst-case error under the RIP, they confirm that the Gelfand width must be bounded above by the performance of these specific, realizable algorithms.

Key Results

The primary contribution of this work is the proof that for $0 < p \leq 1$ and $p < q \leq 2$, the Gelfand width $d^m(B_p^N, \ell_q^N)$ scales as:

$$ d^m(B_p^N, \ell_q^N) \approx \min\left\{1, \frac{\ln(N/m)+1}{m}\right\}^{1/p - 1/q} $$

This result is significant for several reasons:

  1. The Universal Log-Term: It rigorously proves that any stable measurement and reconstruction scheme requires the number of measurements $m$ to scale at least as $s \ln(N/s)$, where $s$ is the signal sparsity and $N$ is the ambient dimension.
  2. Weak-$\ell_p$ Extension: The authors extend these sharp asymptotic bounds to weak-$\ell_p$-balls for $p < 1$, a novel result that broadens the scope of compressible signal models.
  3. Measurement Limits: The work explicitly calculates the minimum measurements required for exact recovery, proving the requirement $m \geq c_1 p s \ln(N/(c_2 s))$.

Discussion and Future Work

While the bounds are tight for the regime $q \leq 2$, the $q > 2$ regime remains partially unresolved. Although the lower bound technically extends to $q > 2$, it is unlikely to be optimal. Drawing from known behaviors at $p=1$, the authors suspect the scaling for $q > 2$ should drop the $1/q$ dependence and scale closer to $m^{-1/2}$.

Additionally, while the results for weak-$\ell_p$-balls are sharp for $p < 1$, the case of $p = 1$ (weak-$\ell_1$-balls) remains an open problem. Current compressive sensing arguments introduce a potentially suboptimal log factor in this specific case, suggesting that further refinement of the geometric tools is necessary to capture the exact behavior of weak-$\ell_1$ limits.

Summary updated

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\leq 1$ and $p<q \leq 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 $\textbackslash\{\}ell\_p$-balls for $0<p\textbackslash\{\}leq 1$}},
  journal = {Journal of Complexity},
  year = {2010},
  doi = {10.1016/j.jco.2010.04.004},
}
Figure