[talks] S Jafarpour preFPO
mml at CS.Princeton.EDU
Fri Feb 4 11:52:26 EST 2011
Sina Jafarpour will present his preFPO on Friday February 11 at 2PM in Room 402. The members
of his committee are: Robert Calderbank; advisor, Rob Schapire and Ingrid Daubechies (Duke); readers,
and David Blei and Amit Singer (PACM and Math); non-readers. Everyone is invited to attend his
talk. His abstract follows below.
Title: Deterministic Compressed Sensing
The central goal of compressed sensing is to capture attributes of a signal using very few measurements.
The initial publications by Donoho and by Candes and Tao have been followed by applications to image
compression, data streaming, medical signal processing, digital communication and many others. The
emphasis has been on random sensing but the limitations of this framework include performance guarantees,
storage requirements, and computational cost. This talk will describe two deterministic alternatives.
The first is based on expander graphs. We show that by reformulating signal reconstruction as a zero-sum game
we can efficiently recover any sparse vector. We also demonstrate resilience to Poisson noise.
The second is based on error correcting codes. We show that deterministic sensing matrices based on second
order Reed Muller codes optimize average case performance. We also describe a very simple algorithm, one-step
thresholding, that succeeds where more sophisticated algorithms, developed in the context of random sensing,
The talk is based on joint work with Waheed Bajwa, Robert Calderbank, Volkan Cevher, Marco Duarte, Zachary
Harmany, Stephen Howard, Maxim Raginsky, Rob Schapire, and Rebecca Willett.
More information about the talks