Signal Processing Seminar

Title:  On the Interplay Between Coding Theory and Compressed Sensing

Speaker:  Professor Olgica Milenkovic
University of Illinois
 
Wednesday, February 20, 2008
4:00 PM to 5:00 PM
Room 2269 Beckman
Signal Processing Seminar
 
Contact: Barbara Horner
Invited: Public is Welcome
________________________________________
Abstract: 

Compressed sensing (CS) is a signal processing technique that allows for accurate 
recovery of sparse data-vectors based on a small number of linear measurements. 
In its most basic form, robust CS can be viewed as a specialized error-control coding 
scheme in which the data alphabet does not necessarily have the structure of a finite 
field and where the notion of a “parity-check” is replaced by a more general 
functionality. We describe how to combine and extend the classical CS and Euclidean 
superimposed coding paradigms in terms of introducing new minimum distance and
codeword-composition constraints. In this setting, we derive fundamental lower and 
upper bounds on the achievable “compression ratio” for this type of constrained 
compressed sensing (CCS) schemes using classical coding-theoretic techniques. We
 also show that Euclidean superimposed codes, a new class of weighted Euclidean 
superimposed codes, as well as spherical codes, can be used for deterministic CCS 
designs. Furthermore, we demonstrate that sparse reconstruction in the presence of 
noise can be performed via low-complexity correlation-maximization algorithms. Our 
problem analysis is motivated by a myriad of applications ranging from compressed 
sensing microarray designs, reliability-reordering decoding of linear block-codes, 
identification in multi-user communication systems, and fault tolerant computing. 

This is a joint work with Wei Dai from the ECE Department at UIUC.