The Johns Hopkins University

Whiting School of Engineering

Department of Electrical and Computer Engineering

Fast Compressive Sampling

Seminar By

Thong Do

Graduate Research Assistant

Electrical and Computer Engineering

Abstract:

In the conventionally uniform sampling framework, the Shannon/Nyquist theorem tells us to sample a signal at least two times faster than its bandwidth so that the original signal can be perfectly reconstructed from its samples. Recently, the new generalized sampling framework - Compressive Sampling, is proposed to show that the Shannon/Nyquist theorem is, indeed, over-pessimistic for a large family of sparse signals, i.e. signals that have sparse representations under some linear transformations. The Compressive Sampling framework simply states that if a signal is sparse, we can acquire it at a rate significantly below the Nyquist without losing its information. This striking result is believed to open a wide area of potential applications such as a new data acquisition method that translates analog signal into digital information using fewer sensors than what was considered necessary. Compressive Sampling may be regarded as the new paradigm for sampling and compressing data simultaneously.

The key components of Compressive Sampling framework include a measurement ensemble at the encoder that is highly incoherent with the signal and a nonlinear reconstruction at the decoder to find the sparsest solution. The incoherent measurements are often realized by random projections while the nonlinear reconstructions are often based on L1-norm optimization or greedy algorithms. Several universally incoherent measurement ensembles have been proposed such as random matrices with i.i.d Gaussian/Bernoulli entries. However, these measurement ensembles have some major drawbacks in practical applications: huge memory buffering for storage of matrix elements and high computational complexity due to their completely unstructured nature.

In this work, we propose a novel fast compressive sampling algorithm that is based on a new concept of structurally random ensembles. The new proposed algorithm not only enables the system to compressively sample signals very fast but also requires very low complexity with other highly desired features for practical applications such as: integer friendliness, streaming capability. Surprisingly, this novel algorithm is also proposed to solve a closely related problem of high dimensional reduction in theoretical computer sciences.

Friday, December 7, 2007

11:00 a.m.

Barton 114

Refreshments will be served at 10:45 a.m.

FOR DISABILITY INFORMATION

CONTACT: Candace Abel (410) 516-7031 cabel@jhu.edu