IC Monday Seminar : “A New Characterization of Compressed Sensing Limits”
Event details
| Date | 06.06.2011 |
| Hour | 16:15 |
| Speaker | Galen Reeves - UC Berkeley and EPFL invited by Prof. Michael Gastpar |
| Location |
INM 202
|
| Category | Conferences - Seminars |
Abstract: 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. Bio: Galen Reeves is currently a postdoctoral researcher in the School of Computer and Communication Sciences, EPFL, working with Michael Gastpar. He received the B.S. degree in electrical and computer engineering from Cornell University in 2005 and the M.S. degree in electrical engineering and computer sciences from the University of California at Berkeley (UC Berkeley) in 2007. His Ph.D. thesis is titled "A New Characterization of Compressed Sensing Limits," and his research interests include statistical signal processing, compressed sensing, information theory, and machine learning. Beginning in Fall 2011, he will be a VIGRE Postdoctoral Scholar in the Department of Statistics, Stanford University, working with David Donoho.
Links
Practical information
- General public
- Free
Contact
- Christine Moscioni