Compressed Sensing Meets Information Theory

Google Tech Talk October 7, 2009 ABSTRACT Presented by Dror Baron, Visiting Scientist, Technion - Israel Institute of Technology. Traditional signal acquisition techniques sample band-limited analog signals above the Nyquist rate, which is related to 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 several investigations along these lines. First, distributed compressed sensing (DCS) provides new distributed signal acquisition algorithms that exploit both intra- and inter-signal correlation structures in multi-signal ensembles. DCS is immediately applicable in sensor networks. Next, we leverage the remarkable success of graph reduction algorithms and LDPC channel codes to design low-complexity CS reconstruction algorithms. Linear measurements play a crucial role not only in compressed sensing but in disciplines such as finance, where numerous noisy measurements are needed to estimate various statistical characteristics. Indeed, many areas of science and engineering seek to extract information from linearly derived measurements in a computationally feasible manner. Advances toward a unified theory of linear measurement systems will enable us to effectively process the vast amounts of data being generated in our dynamic world.