Corruption, Justice and Democracy in Compressive Sensing

A core problem in compressive sensing concerns how to stably recover sparse signals from a small number of measurements in the presence of noise. It is known that if the noise can be bounded in norm by $\epsilon$, then standard algorithms recover sparse signals with error at most $C \epsilon$. However, these algorithms perform suboptimally when the measurement noise is structured. In my talk I will describe a hierarchy of structured noise models. I will begin by describing methods for filtering out a corrupting signal from a set of measurements where the corruption consists of a sparse signal with known support. After describing some simple applications of this method, I will then consider the case where the measurements are corrupted by sparse noise with unknown support. I will describe a simple algorithm, dubbed Justice Pursuit, that can accurately identify the corrupted measurements and recover the underlying signal. Justice Pursuit handles unbounded errors, has no input parameters, and is easily implemented via standard recovery techniques. I will conclude by observing that the main results concerning corruption and justice can be combined to demonstrate that random matrices are democratic, meaning that when using random measurement matrices compressive sensing is robust to the loss of a small number of arbitrary measurements.
Mark A. Davenport received the B.S.E.E. degree in Electrical and Computer Engineering in 2004 and the M.S. degree in Electrical and Computer Engineering in 2007, both from Rice University. He is currently a Ph.D. student in the Department of Electrical and Computer Engineering at Rice. His research interests include compressive sensing, nonlinear approximation, and the application of low-dimensional signal models to a variety of problems in signal processing and machine learning. In 2007, he shared the Hershel M. Rich Invention Award from Rice for his work on the single-pixel camera and compressive sensing. He is also co-founder and an editor of Rejecta Mathematica.