Talk 6824 data/Fall

Duke Computer Science Colloquia
Wednesday, December 2, 2009, 11:45am, D106 LSRC
Robert Calderbank (Princeton University)
Deterministic Compressive Sensing

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 5:21am Wednesday, April 24, 2024 by Mcal. Top * Reload * Login