Compressive Sampling (CoSa) offers a new paradigm for acquiring
signals that are compressible with respect to an orthobasis. The major
algorithmic challenge in CoSa is to approximate a compressible signal
from noisy samples. Until recently, all provably correct reconstruction
techniques have relied on large-scale optimization, which tends to be
computationally burdensome.

This talk describes a new iterative, greedy recovery algorithm, called
CoSaMP that delivers the same guarantees as the best optimization-based
approaches.
Moreover, this algorithm offers rigorous bounds on computational cost
and storage. It is likely to be extremely efficient for practical
problems because it
requires only matrix--vector multiplies with the sampling matrix. For
some cases of interest, the running time is just O(N*log^2(N)), where
N is the length of the signal.