  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.
