TL;DR
This paper introduces "Corrupted Sensing," a framework for recovering structured signals (like sparse vectors or low-rank matrices) from measurements that are not just noisy, but systematically corrupted. By using a geometric approach based on Gaussian complexity, the authors provide sharp theoretical bounds for when convex optimization can successfully separate a signal from structured corruption, matching empirical results with high precision.
What Problem Does This Paper Address?
In standard compressed sensing, we try to recover a signal $x$ from a small number of measurements $y = \Phi x + z$, where $z$ is small, unstructured noise. However, in many real-world scenarios—like failing sensors in a network or video background subtraction—measurements suffer from structured corruption. This means some measurements might be completely wrong (large magnitude), but the pattern of wrongness is structured (e.g., only a few sensors are broken, or the corruption is "block-sparse").
The challenge is "deconvolution": how do we disentangle the true signal from the structured corruption when we only observe their sum? Previous work handled specific cases (like sparse signals with sparse corruption), but this paper seeks a general theory that works for any pair of structures.
Methods
The authors employ a convex programming approach. They analyze two main types of optimization problems:
- Constrained Programs: These minimize the complexity of the signal while capping the complexity of the corruption (or vice versa), assuming some prior knowledge of the structure.
- Penalized Programs: These use a regularized approach (similar to Lasso) to trade off between signal complexity and corruption complexity using a penalty parameter $\lambda$.
The "secret sauce" of their analysis is the use of Gaussian complexity and Gaussian distance. These are geometric tools that measure the "width" or "size" of the set of directions in which a signal can be perturbed while still appearing "simple" to a convex norm (like the $\ell_1$ norm for sparsity or the trace norm for low-rank matrices).
Datasets
As a theoretical paper, the authors do not use standard large-scale datasets (like ImageNet). Instead, they evaluate their guarantees using synthetic simulations:
- Measurement Matrices: i.i.d. Gaussian matrices $\Phi$.
- Signals: Binary vectors, sparse vectors, and low-rank matrices.
- Corruptions: Sparse vectors and block-sparse vectors.
- Noise: Added unstructured Gaussian noise to test the "stability" of the recovery.
Key Insights and Ideas
- The Additive Complexity Rule: The fundamental insight is that recovery is possible if the number of measurements $n$ exceeds the sum of the squared Gaussian complexities of the signal and the corruption. Essentially, the "budget" of measurements must be larger than the combined "dimensionality" of the two structures.
- New, Sharper Bounds: The authors derived new closed-form bounds for the Gaussian complexity of sparse and block-sparse vectors. Notably, their new bounds are tighter than previous literature when the signal is "nearly dense" (i.e., not extremely sparse), which is critical for understanding the limits of these systems.
- Geometric Phase Transitions: The paper demonstrates that there is a "sharp" boundary (a phase transition) where recovery goes from impossible to almost certain. Their theoretical "red line" predicts this empirical boundary almost perfectly in simulations.
- Asymmetry: While signal and corruption are both "structured," they aren't treated identically. The signal is modulated by the measurement matrix $\Phi$, while the corruption is added directly. This creates a slight but important asymmetry in the recovery guarantees.
Key Results
- Exact Recovery: In the noiseless case, the authors provide explicit formulas for the number of measurements needed to perfectly separate the signal from corruption. For example, in binary signal recovery with sparse corruption, they show recovery is possible even if ~19.3% of measurements are corrupted.
- Stable Recovery: When unstructured noise is added, the recovery error is shown to be proportional to the noise level $\delta$, proving the method is robust and doesn't "explode" under small perturbations.
- Parameter Tuning: For penalized programs, they provide a specific formula for the penalty parameter $\lambda$ (based on the ratio of Gaussian distances) that achieves near-optimal performance without needing to know the exact sparsity levels in advance.
Limitations and Future Work
- Gaussian Assumption: The current theoretical guarantees rely heavily on the measurement matrix $\Phi$ having i.i.d. Gaussian entries. Extending this to more practical matrices (like subsampled Fourier transforms) remains an open challenge.
- Adversarial Independence: The theory assumes the signal and corruption are chosen independently of the measurement matrix. If an attacker knows $\Phi$ and chooses the corruption $v$ specifically to "hide" in the null space of $\Phi$, these guarantees might not hold.
- Non-Gaussian Measurements: The authors suggest that future work should explore "incoherence conditions" that would allow these results to generalize to non-stochastic or deterministic measurement settings.
Summary updated