Compressed Sensing: On the Interplay Between Coding Theory and Compressed Sensing

Added to the Calendar, Olgica Milenkovic, will make a presentation entitled: "On the Interplay Between Coding Theory and Compressed Sensing" tomorrow at the University of Illinois at Urbana Champaign.

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.
Date Feb 20, 2008
Time 4:00 pm
Location 2269 Beckman Institute
Sponsor Department of Electrical and Computer Engineering