Abstract
This paper investigates the robustness of Quadratically-Constrained Basis Pursuit (QCBP) in scenarios where the noise level is unknown. By introducing a theoretical framework based on $\ell^1$-quotients, the authors demonstrate that QCBP exhibits graceful degradation when measurement error exceeds the pre-set tolerance $\eta$. The findings are validated for Gaussian matrices and Bounded Orthonormal Systems, bridging the gap between theoretical guarantees and practical applications in compressed sensing.
Introduction
In Compressed Sensing (CS), the goal is to recover a sparse signal $x$ from a small number of noisy measurements $y = Ax + e$. The standard tool for this is Quadratically-Constrained Basis Pursuit (QCBP), which seeks the sparsest signal fitting the data within a noise threshold $\eta$.
However, most mathematical guarantees for QCBP assume an a priori bound on the noise (i.e., $\|e\|_2 \leq \eta$). In practice, noise levels are often unknown or underestimated due to sensor limitations or model mismatches. This research addresses a critical question: what happens to signal recovery when the noise is larger than expected? The authors prove that QCBP is robust even in these "noise-blind" scenarios, showing that recovery error degrades gracefully rather than exploding.
Theoretical Framework
The authors develop a new framework to analyze noise-blind scenarios using two primary components:
- Quotient Properties: They introduce mathematical constants called $\ell^1$-quotients and simultaneous quotients. These values measure how much a sensing matrix amplifies measurement errors during recovery.
- Abstract Robustness Link: A fundamental theorem is established showing that if a decoder is "robustly instance optimal" (working perfectly when noise is known), it is automatically stable when noise is unknown, provided the matrix has a well-behaved quotient.
This theory is applied to two major classes of sensing matrices: Random Gaussian Matrices (the theoretical gold standard) and Bounded Orthonormal Systems (BOS), which include practical applications like subsampled Fourier transforms used in MRI.
Key Insights and Results
The core finding is the principle of Graceful Degradation. The recovery error is bounded by standard terms plus a new term proportional to $\max\{\|e\|_2 - \eta, 0\}$. This implies that if the noise $e$ exceeds the threshold $\eta$, the penalty is only proportional to the excess noise.
Empirical Validation
Numerical experiments confirm the theoretical predictions. As shown in the figure below, QCBP variants maintain high accuracy across different measurement models, even as the number of measurements $m$ increases.
- Gaussian Robustness: For Gaussian matrices, recovery is extremely stable, with error increasing only by a small constant factor relative to excess noise.
- BOS Limitations: For Fourier-based measurements, robustness is maintained, though error is amplified by a polylogarithmic factor involving $\log(N)$.
- Polynomial Approximation: The paper provides a theoretical explanation for why $\ell^1$ minimization effectively approximates high-dimensional functions in uncertainty quantification, even with unknown truncation errors.
Discussion and Future Work
While the paper establishes a strong foundation for noise-blind recovery, several challenges remain. The current theory for Bounded Orthonormal Systems (like Fourier or Chebyshev) primarily holds in the "low sparsity" regime where $s < \sqrt{N}$. Extending these guarantees to higher sparsity levels is a key area for future research. Additionally, while the authors calculated distortion parameters for Chebyshev polynomials, finding general upper bounds across all BOS types remains an open problem. Finally, numerical results suggest that theoretical bounds for the $\ell^1$-quotient may be conservative, hinting that even tighter guarantees are possible.
Summary updated