Compressed Sensing Meets Information Theory

Traditional signal acquisition techniques sample band-limited analog signals above the Nyquist rate, which is twice the highest analog frequency in the signal. Compressed sensing (CS) is based on the revelation that optimization routines can reconstruct a sparse signal from a small number of linear projections of the signal. Therefore, CS-based techniques can acquire and process sparse signals at much lower rates. CS offers tremendous potential in applications such as broadband analog-to-digital conversion, where the Nyquist rate exceeds the state of the art.

Information theory has numerous insights to offer CS; I will describe investigations along these lines. We developed an information-theoretic characterization of CS performance, and have proved that belief propagation (BP) is asymptotically optimal when using sparse measurement matrices. Although our CS-BP algorithm reconstructs the input signal well, it is a bit slow in practice, and I describe much faster algorithms that are related to group testing. I will conclude the talk by relating CS to other areas of science and engineering where we seek to extract information from linearly derived measurements in a computationally feasible manner.