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 po