Corrupted Sensing: Novel Guarantees for Separating Structured Signals

Rina Foygel, Lester W. Mackey

Abstract

We study the problem of corrupted sensing, a generalization of compressed sensing in which one aims to recover a signal from a collection of corrupted or unreliable measurements. While an arbitrary signal cannot be recovered in the face of arbitrary corruption, tractable recovery is possible when both signal and corruption are suitably structured. We quantify the relationship between signal recovery and two geometric measures of structure, the Gaussian complexity of a tangent cone and the Gaussian distance to a subdifferential. We take a convex programming approach to disentangling signal and corruption, analyzing both penalized programs that trade off between signal and corruption complexity, and constrained programs that bound the complexity of signal or corruption when prior information is available. In each case, we provide conditions for exact signal recovery from structured corruption and stable signal recovery from structured corruption with added unstructured noise. Our simulations demonstrate close agreement between our theoretical recovery bounds and the sharp phase transitions observed in practice. In addition, we provide new interpretable bounds for the Gaussian complexity of sparse vectors, block-sparse vectors, and low-rank matrices, which lead to sharper guarantees of recovery when combined with our results and those in the literature.

Introduction

Standard compressed sensing focuses on recovering a structured signal $x$ from noisy measurements $y = \Phi x + z$, where $z$ is small, unstructured noise. However, many practical applications—such as sensor network failures or video background subtraction—involve structured corruption. In these cases, measurements are not just noisy but systematically incorrect. This paper introduces a general framework for "Corrupted Sensing," where the goal is to disentangle a structured signal from structured corruption $v$ in the observation model $y = \Phi x + v + z$.

Methods

The authors utilize convex optimization to perform this deconvolution. They analyze two primary formulations:

  1. Constrained Programs: Minimizing signal complexity (e.g., $\ell_1$ norm) while capping corruption complexity, or vice versa.
  2. Penalized Programs: A regularized approach that minimizes a weighted sum of signal and corruption complexities, similar to the Lasso.

The theoretical analysis relies on geometric tools: Gaussian complexity and Gaussian distance. These metrics quantify the "width" of the tangent and normal cones associated with the convex norms used for recovery. Recovery is shown to be possible when the measurement budget $n$ exceeds the combined "dimensionality" (sum of squared Gaussian complexities) of the signal and the corruption.

Key Theoretical Contributions

A major contribution of this work is the derivation of new, sharper closed-form bounds for the Gaussian complexity of various structures, including sparse vectors, block-sparse vectors, and low-rank matrices. These bounds are significantly tighter than those in previous literature, particularly as signals become less sparse.

Comparison of Gaussian distance bounds for sparse vectors. The new closed-form bound (red dots) significantly improves upon prior literature (blue dashed), closely tracking the optimal bound (black line).

As shown in the table below, the new bounds provide explicit formulas that fill gaps in existing theory and offer more precise recovery guarantees.

Summary of prior and new Gaussian squared complexity bounds. The new bounds provide tighter estimates for sparse and low-rank models, enabling more accurate recovery predictions.

Results and Empirical Validation

The paper demonstrates that theoretical bounds align almost perfectly with empirical "phase transitions" observed in synthetic simulations. Key findings include:

  • Exact Recovery: In noiseless settings, the signal and corruption can be perfectly separated if the measurement count is sufficient. For instance, binary signals can be recovered even when nearly 20% of measurements are corrupted.
  • Stability: The recovery error scales linearly with the level of unstructured noise $\delta$, ensuring the method is robust to small perturbations.
  • Parameter Tuning: The authors provide a principled way to set the penalty parameter $\lambda$ in regularized programs based on the ratio of Gaussian distances, achieving near-optimal performance.

Conclusion and Future Work

This work provides a unified geometric framework for understanding the limits of signal recovery under structured corruption. While the current theory assumes i.i.d. Gaussian measurement matrices, it sets the stage for future research into more practical, non-stochastic measurement settings and adversarial scenarios where corruption might be strategically chosen to interfere with the signal.

Summary updated

Abstract

We study the problem of corrupted sensing, a generalization of compressed sensing in which one aims to recover a signal from a collection of corrupted or unreliable measurements. While an arbitrary signal cannot be recovered in the face of arbitrary corruption, tractable recovery is possible when both signal and corruption are suitably structured. We quantify the relationship between signal recovery and two geometric measures of structure, the Gaussian complexity of a tangent cone and the Gaussian distance to a subdifferential. We take a convex programming approach to disentangling signal and corruption, analyzing both penalized programs that trade off between signal and corruption complexity, and constrained programs that bound the complexity of signal or corruption when prior information is available. In each case, we provide conditions for exact signal recovery from structured corruption and stable signal recovery from structured corruption with added unstructured noise. Our simulations demonstrate close agreement between our theoretical recovery bounds and the sharp phase transitions observed in practice. In addition, we provide new interpretable bounds for the Gaussian complexity of sparse vectors, block-sparse vectors, and low-rank matrices, which lead to sharper guarantees of recovery when combined with our results and those in the literature.
BibTeX
@article{foygel2014corrupted,
  author = {Rina Foygel and Lester W. Mackey},
  title = {{Corrupted Sensing: Novel Guarantees for Separating Structured Signals}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  url = {https://openreview.net/forum?id=IQk0yglUAon},
}
Figure