Robustness to Unknown Error in Sparse Regularization

Simone Brugiapaglia, Ben Adcock

TL;DR

This paper bridges the gap between theoretical compressed sensing and real-world practice by proving that Quadratically-Constrained Basis Pursuit (QCBP) is robust even when the noise level is unknown. The authors demonstrate that if your measurement error exceeds your pre-set tolerance, the recovery error doesn't explode; instead, it degrades gracefully and predictably.

What Problem Does This Paper Address?

In the world of Compressed Sensing (CS), we try 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 looks for the "simplest" (most sparse) signal that fits the data within a noise threshold $\eta$.

The catch? Almost all existing mathematical guarantees for QCBP assume you know an a priori bound on the noise (i.e., $\|e\|_2 \leq \eta$). In reality, noise is messy. It comes from physical sensors, model mismatches, or numerical rounding errors, and we rarely know its exact magnitude. If you set your threshold $\eta$ too low, the standard theory provides no guarantees. This paper asks: What happens to our signal recovery when the noise is larger than we expected?

Methods

The authors develop a new theoretical framework to analyze "noise-blind" scenarios. The core of their approach involves:

  1. Quotient Properties: They introduce mathematical constants called $\ell^1$-quotients and simultaneous quotients. These values essentially measure how much a sensing matrix "amplifies" measurement errors during the recovery process.
  2. Abstract Robustness Link: They prove a fundamental theorem showing that if a decoder is "robustly instance optimal" (meaning it works perfectly when noise is known), it is automatically stable and robust when noise is unknown, provided the matrix has a well-behaved quotient.
  3. Matrix Analysis: They apply this theory to two major classes of sensing matrices:
  4. Random Gaussian Matrices: The "gold standard" in CS theory.
  5. Bounded Orthonormal Systems (BOS): This includes practical cases like subsampled Fourier transforms (used in MRI) and Chebyshev polynomial expansions.

Datasets

As a theoretical mathematics paper, it does not use traditional "datasets" like ImageNet. Instead, the authors evaluate their theory using synthetic measurement models:

  • Random Gaussian measurements: Independent standard normal entries.
  • Partial Discrete Fourier Transform: Subsampled rows of a Fourier matrix.
  • Nonharmonic Fourier measurements: Measurements taken at non-integer frequencies.
  • Chebyshev Polynomials: Used for approximating smooth functions from pointwise samples.

Key Insights and Ideas

  • Graceful Degradation: The most important "aha" moment is the form of the new error estimate. The recovery error is bounded by the standard terms plus a new term: $\text{constant} \times \max\{\|e\|_2 - \eta, 0\}$. This means if the noise $e$ exceeds the threshold $\eta$, the penalty is only proportional to the excess noise.
  • The Power of Quotients: The authors show that the "Quotient Property"—originally a niche concept in functional analysis—is actually the key to understanding why QCBP works so well in practice despite unknown noise.
  • Threshold Calibration: The results suggest that while QCBP is robust, there is still a significant benefit to estimating the noise level as accurately as possible to minimize the error constant.

Key Results

  • Gaussian Robustness: For Gaussian matrices, the recovery is extremely stable. The error only increases by a small constant factor relative to the excess noise.
  • BOS Limitations: For Bounded Orthonormal Systems (like Fourier measurements), the robustness is still there, but the error is amplified by a "polylogarithmic" factor (a factor involving $\log(N)$).
  • Empirical Validation: Numerical experiments confirm the theory. For example, in Fourier-based recovery, the algorithm remains remarkably accurate even when the noise is significantly higher than the chosen $\eta$.
  • Polynomial Approximation: The paper provides the first theoretical explanation for why $\ell^1$ minimization is so effective for approximating high-dimensional functions in uncertainty quantification, even when truncation errors are unknown.

Limitations and Future Work

  • Sparsity Regime for BOS: For matrices like Fourier or Chebyshev, the current theory only holds in the "low sparsity" regime where the number of non-zero entries $s$ is roughly less than $\sqrt{N}$. Extending this to higher sparsity levels remains an open challenge.
  • Distortion Parameters: The bounds for BOS depend on a "distortion parameter" $\xi$. While the authors calculated this for Chebyshev polynomials, finding a general upper bound for $\xi$ across all types of Bounded Orthonormal Systems is still an unsolved problem.
  • Sharpness of Bounds: Numerical results suggest that the theoretical bounds for the $\ell^1$-quotient might be too conservative in some cases, suggesting that even tighter guarantees might be 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 the 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. Then, we 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 the 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},
}

Loading related content...

Figure