Jump to Content

ITR Seminar Announcement

Presenter(s)Dr Pascal Vontobel
TitleA Connection Between Channel Coding Linear Programming Decoding and Compressed Sensing Linear Programming Decoding
DateWednesday 11 Nov 2009
Time13:00
LocationSPRI Lecture Theatre (1-6)

Seminar Abstract

Recently there has been substantial interest in the theory of recovering sparse approximations of signals that satisfy linear measurements. Compressed (or compressive) sensing research [Donoho, Candes/Tao, etc.] has developed conditions for measurement matrices under which (approximately) sparse signals can be recovered by solving a linear programming relaxation of the original NP-hard combinatorial problem. Interestingly, in one of the first papers in this area, Candes and Tao presented a setup they called "decoding by linear programming," henceforth called CS-LPD, where the (approximately) sparse signal corresponds to real-valued noise that is added to a real-valued signal that is to be recovered in a hypothetical communication problem. At about the same time, in an independent line of research, Feldman, Wainwright, and Karger considered the problem of decoding a binary linear code that is used for data communication over a binary- input memoryless channel, a problem that is also NP-hard in general. Feldman et al. formulated this channel coding problem as an integer linear program, along with presenting a linear programming relaxation for it, henceforth called CC-LPD. CS-LPD and CC-LPD (and the setups they are derived from) are *formally* very similar, however, it is rather unclear if there is a connection beyond this formal relationship. In fact Candes and Tao in their original paper asked the following question: ``... In summary, there does not seem to be any explicit known connection with that line of work (i.e., Feldman et al.'s work) but it would perhaps be of future interest to explore if there is one.'' In this talk we present such a connection between CS-LPD and CC-LPD. The general form of our results is that if a given binary parity-check matrix is "good" for CC-LPD then the same matrix (considered over the reals) is a "good" measurement matrix for CS-LPD. The notion of a "good"

Presenter Biography

Pascal O. Vontobel received the Diploma degree in electrical engineering in 1997, the Post-Diploma degree in information techniques in 2002, and the Ph.D. degree in electrical engineering in 2003, all from ETH Zurich, Zurich, Switzerland. From 1997 to 2002, he was a Research and Teaching Assistant at the Signal and Information Processing Laboratory at ETH Zurich. After being a Postdoctoral Research Associate at the University of Illinois at Urbana-Champaign, at the University of Wisconsin-Madison (Visiting Assistant Professor), and at the Massachusetts Institute of Technology, he joined the Information Theory Research Group at Hewlett-Packard Laboratories in Palo Alto, CA, in the summer of 2006 as a research scientist. His research interests lie in information theory, communications, and signal processing. He has been on the technical program committees of several international conferences, he has recently co-organized a BIRS workshop in Banff on "Applications of

Back to seminar list