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.
On the engineering side, our analysis answers key engineering questions: Is it better to increase SNR or take more measurements? Is a given algorithm good enough? What accuracy can be attained? On the mathematical side, our results validate certain phase transitions predicted by the powerful, but heuristic, replica method from statistical physics.
Galen Reeves is currently a post-doctoral associate in the Statistics Department at Stanford University, advised by David Donoho. He received a Bachelor's degree in Electrical and Computer Engineering from Cornell University in 2005, and a Master's degree and Ph.D. in Electrical Engineering and Computer Sciences from UC Berkeley in 2007 and 2011 respectively. His research interests include statistical signal processing, high-dimensional statistics, information theory, compressed sensing, and machine learning.