Pfister Receives 2013 NSF Grant

Title: Design and Analysis of Novel Compressed Sensing Algorithms via Connections with Coding Theory

Program: NSF CISE CCF Award in 2013

Abstract: Compressed sensing (CS) is a rapidly advancing area of signal processing and statistics that has the potential to radically change the way that analog signals are transformed into digital signals. The main idea is to acquire a sparse signal from a very small number of measurements using a specialized sampling and reconstruction process. Since one promising application of CS is medical imaging, improvements in CS systems are also expected to advance real-world healthcare applications. In this project, the investigators will study the fundamental connection between error-correcting codes (ECC) and CS and leverage recent advances in ECC to design improved CS measurement and reconstruction systems.

In particular, the connection between linear-programming (LP) decoding of binary linear codes and LP reconstruction will be used to develop a non-asymptotic theory for the design and analysis of CS algorithms and measurement matrices. The first part of the project will focus on novel relaxations of the CS reconstruction problem that allow non-convex regularization and iterative solution. The second part of the project will focus on applying the theory of pseudo-codewords, which was originally developed to understand iterative and LP decoding of binary linear codes, to achieve a non-asymptotic analysis of iterative reconstruction algorithms for CS. The third part of the project will focus on exploiting additional signal structure (i.e., beyond sparsity) that exists in high-contrast imaging applications such as angiograms.

The full details can be found at