Compressed Sensing to the Limits: Bounds, Algorithms, and Wireless Applications

Sparsity has always been an underlying theme in the natural world.
The prevalence of such models in a variety of fields — from
economics to biology to engineering — has recently increased.
This is largely due to advances in optimization, nonlinear
estimation, and random matrix theory, leading to a large number of
theories and algorithms that fall under the broad umbrella of
the term "compressive sensing" .

Nevertheless, certain fundamental questions on the ability to
estimate sparse signals in noise remain unanswered. It is a
challenging computational problem, and rigorous quantification
of the performance of various algorithms has been difficult.
This talk considers the problem of recovering the support of
a sparse vector from random linear measurements with noise.
I provide new necessary and sufficient conditions for reliable
detection as a simple function of the signal and noise statistics.
Furthermore, the performance and benefits of various algorithms,
both suboptimal and optimal, in different regimes are analyzed
and contrasted.

I then consider an application to random on-off multiple access
channels for wireless communication. I show that there are
fundamental connections between random access channels, multiuser
detection, and compressed sensing. Exploiting these connections,
it can be shown that sparsity techniques can offer tractable
multiuser detection methods for random access detection with much
better performance than achieved in current engineering practice.
At the same time, leveraging ideas from successive interference
cancellation can lead to improved algorithms for sparsity detection
problems more generally.