IEEE Circuits and Systems Society Joint Chapter of the Vancouver/Victoria Sections

Fast, Efficient, and Practical Algorithms for Compressed Sensing

Speaker: Dr. Trac D. Tran

Department of Electrical and Computer Engineering
The Johns Hopkins University
Baltimore, Maryland

Dates and Locations

Thursday, May 22, 2008, 3:00 pm to 4:00 pm

ASSC-1: Room 10041 (The new building next to the Strand Hall and Bus Exchange)

Simon Fraser University, Burnaby, BC, Canada

Refreshment will be served after the talk.

Please click here to play the WebEx record of Prof. Tran's talk.

PDF file of the talk.

Abstract

In the conventional uniform sampling framework, the Shannon/Nyquist theorem tells us to sample a signal at a rate at least two times faster than its bandwidth for the original signal to be perfectly reconstructed from its samples. Recently, compressed sensing has emerged as a revolutionary signal sampling paradigm which shows that Shannon theorem is indeed overly pessimistic for signals with a high degree of sparsity or compressibility. The compressed sensing framework demonstrates that a small number of random linear projections, called measurements, contains sufficient information for signal reconstruction, even exactly. The two key components of compressed sensing are: (i) the sensing matrix at the encoder must be highly incoherent with the sparsifying signal transformation; and (ii) sophisticated non-linear algorithms such as basis pursuit or orthogonal matching pursuit are employed at the decoder to recover the sparsest signal from the received measurements. 

The first part of this talk gives an overview of the new compressed sensing framework along with the most elegant breakthrough results in the field. The second part focuses on two recent compressed sensing discoveries from the JHU Digital Signal Processing Lab. Particularly, a fast and efficient sampling algorithm for compressed sensing based on structurally random matrices will be presented. Our proposed sampling scheme provides several crucial features for practical implementation: fast computable, memory efficient, streaming capable, and hardware friendly while retaining comparable theoretical performance bounds with current state-of-the-art techniques. Secondly, at the decoder side, we present a novel iterative reconstruction algorithm for compressed sensing called Generalized Orthogonal Matching Pursuit (GOMP) that can adaptively, at each iteration step, admit new atoms to join the current selected set from a small candidate set while discard from the selected set atoms that might be highly regarded in previous steps. Simulation results show that GOMP’s performance far exceeds the best existing iterative algorithms with reasonable complexity overhead. Finally, future research directions in compressed sensing are also discussed if time permits.

Biography of Dr. Trac D. Tran

Trac D. Tran received the B.S. and M.S. degrees from the Massachusetts Institute of Technology, Cambridge, in 1993 and 1994, respectively, and the Ph.D. degree from the University of Wisconsin, Madison, in 1998, all in Electrical Engineering.

In July of 1998, Dr. Tran joined the Department of Electrical and Computer Engineering, The Johns Hopkins University, Baltimore, MD, where he currently holds the rank of Associate Professor. His research interests are in the field of digital signal processing, particularly in sampling, multi-rate systems, filter banks, transforms, wavelets, and their applications in signal analysis, compression, processing, and communications. He was the co-director (with Prof. J. L. Prince) of the 33rd Annual Conference on Information Sciences and Systems (CISS'99), Baltimore, MD, in March 1999. In the summer of 2002, he was an ASEE/ONR Summer Faculty Research Fellow at the Naval Air Warfare Center – Weapons Division (NAWCWD) at China Lake, California. He has served as Associate Editor of the IEEE Transactions on Signal Processing as well as IEEE Transactions on Image Processing. He currently serves as a member of the IEEE Technical Committee on Signal Processing Theory and Methods (SPTM TC).

Dr. Tran received the NSF CAREER award in 2001 and the William H. Huggins Excellence in Teaching Award from The Johns Hopkins University in 2007.

Webcast for the talk

Please click here after 2:45pm on May 22, 2008 to join the WebEx-based webcast for the lecture. The password is "message".

Please click here for a quick guide for WebEx (written by Prof. Jim Cavers).

If we could not establish the webcast due to network problem, we will record the lecture offline using WebEx software and post it on the website later.

Contact

Please contact Dr. Jie Liang (Email: JieL at sfu dot ca) if you have any question.