Signal Processing Seminar


Title:  Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity

Speaker:  Dr. Wei Dai
Postdoctoral Researcher
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign

Date:  Wednesday, March 26, 2008
Time:  4:00 PM to 5:00 PM
Where:  2269 Beckman Institute
 
________________________________________

Abstract: 

Compressed sensing has recently received significant attention in the statistics, signal processing, 
communications, information theory research communities, due to its large potential for practical 
applications. In this talk, we will discuss a new method for reconstruction of sparse signals with 
and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two 
important characteristics: low computational complexity, comparable to that of orthogonal matching 
pursuit techniques, and reconstruction accuracy of the same order as that of linear programming 
optimization methods. The presented analysis shows that in the noiseless setting, the proposed 
algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies 
the restricted isometry property with a constant parameter. In the noisy setting and in the case that 
the signal is not exactly sparse, it can be shown that the mean squared error of the reconstruction 
is upper bounded by constant multiples of the measurement and signal perturbation energies.

The talk is based on a joint work with Prof. Olgica Milenkovic at UIUC.

Biography: 
 
Dr. Wei Dai received his Ph.D. and M.S. degree in Electrical and Computer Engineering from the 
University of Colorado at Boulder in 2007 and 2004 respectively. He is currently a Postdoctoral 
Researcher at the Department of Electrical and Computer Engineering, University of Illinois at 
Urbana-Champaign. His research interests include compressive sensing, bioinformatics, wireless 
communications, information theory, and random matrix theory.