Corrupted Sensing: Novel Guarantees for Separating Structured Signals

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.

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6712045

Cited by in corpus (12)

• A new perspective on least squares under convex constraint
• Beyond Low Rank + Sparse: Multi-scale Low Rank Matrix Decomposition
• A Compressed Sensing Based Decomposition of Electrodermal Activity Signals
• Basis Pursuit Denoise with Nonsmooth Constraints
• Recovery of Structured Signals with Prior Information via Maximizing Correlation
• Robust analysis ${\ell }_1$-recovery from Gaussian measurements and total variation minimization
• On the Error in Phase Transition Computations for Compressed Sensing
• Sample Complexity of Total Variation Minimization
• Living near the edge: A lower-bound on the phase transition of total variation minimization
• Uniform Recovery Bounds for Structured Random Matrices in Corrupted Compressed Sensing
• Quantized Corrupted Sensing with Random Dithering
• Corrupted sensing quantum state tomography