ECE Seminar: A New Characterization of Compressed Sensing Limits
Tuesday, February 19, 2013
11:45 am - 12:45 pm
Hudson Hall 232
Galen Reeves, Ph.D., Department of Statistics, Stanford University
The fact that sparse signals can be recovered from a small number of measurements has important and exciting implications for engineering and statistics. However, despite the vast amount of recent work in the field of compressed sensing, a sharp characterization between what can and cannot be recovered in the presence of noise remains an open problem in general. In this talk, we provide such a characterization for the task of sparsity pattern estimation (also known as support recovery). Using tools from information theory, we find a sharp separation into two problem regimes -- one in which the problem is fundamentally noise-limited, and a more interesting one in which the problem is limited by the behavior of the sparse components themselves. This analysis allows us to identify settings where existing computationally efficient algorithms, such as the LASSO or approximate message passing, are optimal as well as other settings where these algorithms are highly suboptimal. Furthermore, we show how additional structure can make a key difference, analogous to the role of diversity in wireless communications.