Abstract
This paper establishes sharp lower and upper bounds for the Gelfand widths of $\ell_p$-balls in $N$-dimensional $\ell_q^N$-space, where $0 < p \le 1$ and $p < q \le 2$. By utilizing techniques from the field of compressive sensing, the authors resolve a long-standing gap in the literature concerning non-convex quasi-Banach spaces. These results provide fundamental theoretical limits for signal recovery and demonstrate a powerful synergy between classical approximation theory and modern sparse recovery algorithms.
Introduction
In the study of information-based complexity and approximation theory, Gelfand widths serve as a critical metric for understanding the intrinsic difficulty of approximating a set of signals using linear measurements. Specifically, the Gelfand width of an $\ell_p$-ball represents the minimum possible error achievable when reconstructing a signal from $m$ linear measurements in an $N$-dimensional space.
While the asymptotic behavior for the convex case ($p=1$) was well-established by the 1980s through the work of Kashin, Gluskin, and Garnaev, the non-convex case ($p < 1$)—which is essential for modeling highly compressible signals—remained problematic. In 2006, David Donoho proposed bounds for this regime, but his lower bound proof relied on Carl's theorem. This theorem requires duality arguments that are invalid in the quasi-Banach spaces associated with $p < 1$. This paper provides the first rigorous proof for these bounds by bypassing traditional functional analysis in favor of compressive sensing principles.
Methodology: A Compressive Sensing Approach
The authors depart from standard approximation theory proofs by employing the mechanics of sparse recovery to establish geometric bounds. This approach is conceptually elegant: typically, approximation theory is used to prove bounds in compressive sensing, but here the relationship is reversed.
Lower Bound via the Null Space Property
To establish the lower bound, the authors employ a proof by contradiction. They demonstrate that if the Gelfand width were smaller than the proposed bound, it would imply the existence of a measurement matrix capable of recovering $s$-sparse signals with fewer measurements than theoretically allowed. This theoretical minimum is derived using a volumetric and combinatorial analysis of the "$p$-null space property," which characterizes the kernels of matrices that allow for successful $\ell_p$ reconstruction.
Upper Bound via Restricted Isometry
The upper bounds are established using matrices that satisfy the Restricted Isometry Property (RIP), such as Gaussian random matrices. By analyzing the error stability of $\ell_1$-minimization (Basis Pursuit) and $\ell_p$-minimization, the authors show that these algorithms achieve the optimal reconstruction error predicted by the Gelfand width, thereby providing a constructive upper bound.
Key Results
The primary contribution of this work is the derivation of sharp asymptotic bounds for the Gelfand width of order $m$ for the $\ell_p$-ball in $\ell_q^N$ ($0 < p \le 1, p < q \le 2$):
$$ d^m(\ell_p^N, \ell_q^N) \approx \min\left\{1, \frac{\ln(N/m)+1}{m}\right\}^{1/p - 1/q} $$
Furthermore, the paper extends these results to weak-$\ell_p$-balls. This extension is particularly significant for practical applications, as weak-$\ell_p$ spaces more accurately model the power-law decay of coefficients typically found in real-world data, such as the wavelet coefficients of natural images.
Additionally, the authors establish a precise threshold for exact recovery: to recover $2s$-sparse vectors via $\ell_p$-minimization, the number of measurements $m$ must scale as $\Omega(p s \ln(N/s))$. This confirms the existence of a logarithmic penalty that cannot be avoided by any measurement scheme, regardless of the reconstruction algorithm used.
Discussion and Future Work
This research highlights a "two-way street" between pure mathematics and applied signal processing. While approximation theory originally informed the development of compressive sensing, this work demonstrates that algorithmic concepts like RIP and sparse recovery can, in turn, resolve open problems in classical geometry and functional analysis.
One remaining challenge is the $q > 2$ regime. While the current paper provides lower bounds for these cases, they are likely not tight. The authors conjecture that for $q > 2$, the behavior scales as $m^{-1/2}$ (modulo logarithmic factors), but a formal proof remains elusive. Additionally, while the bounds for weak-$\ell_p$ balls are sharp for $p < 1$, the specific behavior of weak-$\ell_1$ balls requires further investigation, as the current RIP-based arguments do not directly translate to the $p=1$ boundary.
Summary updated