A New Characterization of Compressed Sensing Limits

The fact that sparse vectors can be recovered from a small number of linear 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, 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 related to compressed sensing: 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.