UTCS/WNCG Seminar - Galen Reeves/University of California, Berkeley, "A New Characterization of Compressed Sensing Limits", ENS 314

Contact Name: 
Jenna Whitney
Apr 15, 2011 10:00am - 11:00am

There is a sign-up schedule for this event that can be found at



Type of Talk: UTCS/WNCG Seminar

Speaker/Affiliation: Galen

Reeves/University of California, Berkeley

Talk Audience: UTCS Faculty
and Grad Students and ECE

Date/Time: Friday, April 15, 2011, 10:00

Location: ENS 314

Host: Pradeep Ravikumar and Sriram Vishwa


Talk Title: A New Characterization of Compressed Sensing Limits

Talk Abstract:
The fact that sparse vectors can be recovered from a s

mall 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 t

he task of sparsity pattern estimation (also known as support recovery). Us

ing tools from information theory, we find a sharp separation into two pro

blem regimes -- one in which the problem is fundamentally noise-limited, a

nd a more interesting one in which the problem is limited by the behavior o

f the sparse components themselves. This analysis allows us to identify set

tings where existing computationally efficient algorithms, such as the LAS

SO, are optimal as well as other settings where these algorithms are highl

y 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 quest

ions related to compressed sensing: Is it better to increase SNR or take mo

re measurements? Is a given algorithm good enough? What accuracy can be att

ained? On the mathematical side, our results validate certain phase transi

tions predicted by the powerful, but heuristic, replica method from stati

stical physics.

Speaker Bio:
Galen Reeves received the B.S. degree i

n electrical and computer engineering from Cornell University in 2005 and t

he M.S. degree in electrical engineering and computer sciences from the Uni

versity of California at Berkeley (UC Berkeley) in 2007. He is currently co

mpleting his Ph.D. degree in the Department of Electrical Engineering and C

omputer Sciences (EECS) at UC Berkeley. His research interests include stat

istical signal processing, compressed sensing, information theory, and m

achine learning.