Seminar Details
2011-10-18 (14.00) : Robust 1-Bit Compressive Sensing: How the Sign of Random Projections Distinguishes Sparse Vectors
At Euler building
Organized by Mathematical Engineering
Speaker :
Jacques, Laurent
Abstract :
The Compressive Sensing (CS) framework aims to ease the
burden on analog-to-digital converters (ADCs) by reducing the sampling
rate required to acquire and stably recover sparse signals. Practical
ADCs not only sample but also quantize each measurement to a finite
number of bits; moreover, there is an inverse relationship between the
achievable sampling rate and the bit depth.
In this talk, an alternative CS approach that shifts the emphasis from
the sampling rate to the number of bits per measurement is presented. In
particular, we explore the extreme case of 1-bit CS measurements,
which capture just their sign.
Our results come in two flavors. First, we consider ideal reconstruction from noiseless 1-bit measurements and
provide a lower bound on the best achievable reconstruction error. We
also demonstrate that a large class of measurement mappings achieve
this optimal bound.
Second, we consider reconstruction robustness to
measurement errors and noise and introduce the Binary
{\epsilon}-Stable Embedding (B{\epsilon}SE) property, which
characterizes the robustness measurement process to sign changes.
We show the same class of matrices that provide optimal noiseless
performance also enable such a robust mapping.
On the practical side, we introduce the Binary Iterative Hard Thresholding (BIHT) algorithm
for signal reconstruction from 1-bit measurements that offers state-of-the-art performance.
Joint work with J. Laska (Rice Univ., USA), P. Boufounos (MERL, USA)
and R. Baraniuk (Rice Univ., USA)