Duke Computer Science Colloquia
Wednesday, December 2, 2009, 11:45am, D106 LSRC
Robert Calderbank (Princeton University)
Deterministic Compressive Sensing
Abstract:- Compressed Sensing aims to capture attributes of k-sparse
signals using very few measurements. We will describe simple
criteria, that when satisfied by a deterministic sensing
matrix, guarantee successful recovery of all but an
exponentially small fraction of k-sparse signals. These
criteria are satisfied by many families of deterministic
sensing matrices including those formed from subcodes of the
second order binary Reed Muller codes. Our proof of unique
reconstruction uses a variant of the classical McDiarmid
Inequality used in Machine Learning.
We will also describe a reconstruction algorithm for Reed
Muller sensing matrices that takes special advantage of the
code structure. Our algorithm requires only vector-vector
multiplication in the measurement domain, and as a result,
reconstruction complexity is only quadratic in the number of
measurements. This improves upon standard reconstruction
algorithms such as Basis and Matching Pursuit that require
matrix-vector multiplication and have complexity that is
super-linear in the dimension of the data domain.
Biography
Robert Calderbank is Professor of Electrical Engineering and
Mathematics at Princeton University where he directs the
Program in Applied and Computational Mathematics. He joined
Princeton from AT&T where he was Vice President for Research
and responsible for designing the first Research Lab in the
world where the primary focus is data at massive scale.
Advances by Dr. Calderbank have transformed communications
practice in voiceband modems, advanced read channels for
magnetic recording, and wireless systems and have also
opened the door to fault tolerant quantum computation.
Prof. Calderbank is an IEEE Fellow and was honored by the
IEEE Information Theory Prize Paper Award in 1995 and again
in 1999 He was elected to the National Academy of
Engineering in 2005.
Generated at 8:19pm Tuesday, April 23, 2024 by Mcal. Top
* Reload
* Login