Robustness to unknown error in sparse regularization

Simone Brugiapaglia, Ben Adcock

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:

  1. 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.
  2. 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.

Numerical validation of QCBP robustness across different sensing matrices, showing stable recovery error relative to the noise floor.
  • 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

Abstract

Quadratically-constrained basis pursuit has become a popular device in sparse regularization; in particular, in the context of compressed sensing. However, the majority of theoretical error estimates for this regularizer assume an a priori bound on the noise level, which is usually lacking in practice. In this paper, we develop stability and robustness estimates which remove this assumption. First, we introduce an abstract framework and show that robust instance optimality of any decoder in the noise-aware setting implies stability and robustness in the noise-blind setting. This is based on certain sup-inf constants referred to as quotients, strictly related to the quotient property of compressed sensing. We then apply this theory to prove the robustness of quadratically-constrained basis pursuit under unknown error in the cases of random Gaussian matrices and of random matrices with heavy-tailed rows, such as random sampling matrices from bounded orthonormal systems. We illustrate our results in several cases of practical importance, including subsampled Fourier measurements and recovery of sparse polynomial expansions.
BibTeX
@article{brugiapaglia2018robustness,
  author = {Simone Brugiapaglia and Ben Adcock},
  title = {{Robustness to unknown error in sparse regularization}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  url = {https://openreview.net/forum?id=bOMpsXzsGa},
}
Figure