Compressive Sensing over the Grassmann Manifold: a Unified Geometric Framework

Weiyu Xu, Babak HassibiarXiv 2010 · arXiv

Introduction

Compressive Sensing (CS) has revolutionized signal processing by demonstrating that high-dimensional signals can be recovered from a relatively small number of linear measurements, provided the signal is sparse. However, a significant gap has existed between theoretical analysis and practical application. While early theories focused on "ideally sparse" signals (vectors with mostly zero entries), real-world signals are typically "approximately sparse," containing many small but non-zero components.

Traditional tools like the Restricted Isometry Property (RIP) provide robust recovery guarantees but often yield "loose" bounds that underestimate the system's actual capacity. Conversely, neighborly polytope analysis offers sharp bounds for ideal signals but fails to generalize to approximate sparsity or noisy environments. This paper introduces a unified geometric framework that bridges this gap, providing sharp and robust performance bounds.

A Geometric Approach to Null Space Balancedness

The authors shift the analytical focus from the measurement matrix itself to the properties of its null space. They identify "balancedness"—the degree to which a linear subspace avoids alignment with coordinate axes—as the fundamental condition for robust signal recovery via $\ell_1$ minimization.

To quantify this, the framework employs high-dimensional integral geometry. The null space is treated as a point on a Grassmann manifold. The analysis then involves calculating the probability of recovery success by examining the internal and external angles of "skewed cross-polytopes"—geometric representations of the $\ell_1$ unit ball adapted for approximate sparsity. Using Laplace’s method for asymptotic analysis, the authors derive precise "net exponents" that characterize recovery behavior as signal size $n$ approaches infinity.

The Robustness Parameter $C$ and Performance Tradeoffs

A central contribution of this work is the introduction of a robustness constant $C > 1$. This parameter acts as a tunable "knob" for recovery accuracy. When $C$ is close to 1, the framework's bounds converge to the sharp "strong" thresholds established in landmark studies for ideal sparsity. As $C$ increases, the allowable sparsity for guaranteed recovery decreases, but the system becomes more resilient to noise and non-sparse signal components.

Tradeoff between measurement rate ($m/n$) and sparsity ($k/n$) for different robustness constants $C$.

As shown in Figure 1, the relationship between the measurement rate ($m/n$) and the sparsity ratio ($k/n$) is explicitly mapped for various values of $C$. The $C=1$ curve represents the theoretical limit for ideal recovery. As the demand for robustness grows (higher $C$), the phase transition curves shift downward, indicating a necessary reduction in sparsity to maintain recovery stability.

Key Results and Implications

The framework yields several significant results:

  • Sharp Error Bounds: The authors prove that recovery error is bounded by $\|\hat{x} - x\|_1 \leq \frac{2(C+1)\Delta}{C-1}$, where $\Delta$ represents the $\ell_1$ norm of the signal's "tail" (the small, non-sparse components).
  • Threshold Generalization: The work successfully generalizes neighborly polytope results. For instance, at a measurement rate of $\delta \approx 0.55$, the "weak" threshold for ideal recovery is approximately $\zeta \approx 0.0528$. The new framework provides the exact curves for how this threshold evolves under different robustness requirements.
  • Stability Under Noise: The geometric analysis extends to noisy measurements, demonstrating that $\ell_1$ minimization remains stable even when the decoder lacks precise knowledge of the noise variance.

Conclusion

By unifying the sharp analysis of polytope geometry with the robustness required for practical signals, this framework provides a more complete picture of Compressive Sensing performance. While currently optimized for i.i.d. Gaussian measurement matrices and $\ell_1$ minimization, the geometric principles established here offer a foundation for future analysis of structured matrices and alternative recovery algorithms.

Summary updated

Abstract

$\ell_1$ minimization is often used for finding the sparse solutions of an under-determined linear system. In this paper we focus on finding sharp performance bounds on recovering approximately sparse signals using $\ell_1$ minimization, possibly under noisy measurements. While the restricted isometry property is powerful for the analysis of recovering approximately sparse signals with noisy measurements, the known bounds on the achievable sparsity (The "sparsity" in this paper means the size of the set of nonzero or significant elements in a signal vector.) level can be quite loose. The neighborly polytope analysis which yields sharp bounds for ideally sparse signals cannot be readily generalized to approximately sparse signals. Starting from a necessary and sufficient condition, the "balancedness" property of linear subspaces, for achieving a certain signal recovery accuracy, we give a unified \emph{null space Grassmann angle}-based geometric framework for analyzing the performance of $\ell_1$ minimization. By investigating the "balancedness" property, this unified framework characterizes sharp quantitative tradeoffs between the considered sparsity and the recovery accuracy of the $\ell_{1}$ optimization. As a consequence, this generalizes the neighborly polytope result for ideally sparse signals. Besides the robustness in the "strong" sense for \emph{all} sparse signals, we also discuss the notions of "weak" and "sectional" robustness. Our results concern fundamental properties of linear subspaces and so may be of independent mathematical interest.
BibTeX
@misc{xu2010compressive,
  author = {Weiyu Xu and Babak Hassibi},
  title = {{Compressive Sensing over the Grassmann Manifold: a Unified Geometric Framework}},
  year = {2010},
  eprint = {1005.3729},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1005.3729},
}
Figure