Designing optimal sparse signal recovery systems
Friday, April 15, 3PM – 4PM
Anna C. Gilbert, University of Michigan
A sparse signal recovery system consists of a measurement matrix and a decoding algorithm. Given a signal, the system first acquires (linear) observations of the signal via the measurement matrix and then the decoding algorithm takes those measurements and produces an approximation to the original signal. If the signal is compressible or sparse, then the number of measurements we need is considerably fewer than the length of the signal and we say that we have compressive sensing of a signal. The optimal number of measurements is a function of the sparsity and the log of the signal length. A decoding algorithm that outputs a good approximation to the signal (shorter than the original signal) and does so in time that scales sub-linearly with the signal length is an extremely efficient one. In this talk, I will address the question whether we can design compressive sensing systems that achieve the best of all worlds---extremely efficient (sub-linear time) algorithms and using as few signal measurements as possible. This is joint work with Yi Li, Ely Porat, and Martin Strauss.
Hosted by Allison Moore & Kui Ren