CoSaMP: Iterative Signal
Recovery from Incomplete
and Inaccurate Samples
Compressive sampling (CoSa) is a new paradigm for developing data sampling technologies. It is based on the principle that many types of vector-space data are compressible,
which is a term of art in mathematical signal processing.
The key ideas are that randomized dimension reduction preserves the information in a compressible signal and that it
is possible to develop hardware devices that implement this
dimension reduction efficiently. The main computational
challenge in CoSa is to reconstruct a compressible signal
from the reduced representation acquired by the sampling
device. This extended abstract describes a recent algorithm,
called CoSaMP, that accomplishes the data recovery task. It
was the first known method to offer near-optimal guarantees
on resource usage.
1. Wha T iS ComPRESSiVE SamPLinG?
In many applications, the ambient dimension of a data vector does not reflect the actual number of degrees of freedom in that vector. In mathematical signal processing, this
property is captured by the notion of a compressible signal.
Natural images provide a concrete example of compressible signals because we can approximate them accurately
just by summarizing the solid areas (local averages) and the
edges (local differences). This representation allows us to
compress images dramatically without a substantial loss of
visual quality—an idea implemented in the JPEG image coders that we use every day.
Sampling is a generic term for the process of acquiring
data about an object, either in the physical or the virtual
world. There are many different technologies that we use to
collect samples. A ubiquitous piece of sampling hardware is
the CCD array inside a digital camera, which measures the
average light intensity at each small square in the focal plane
of the camera. Other sampling equipment includes X-ray
machines, magnetic resonance imaging (MRI), and analog-to-digital converters.
In most cases, we use sampling to acquire as much infor-
mation as possible about an object of interest. Indeed, when
purchasing a digital camera, we often think that more pixels
are better. But as soon as the image is captured, the camera
invokes compression algorithms to reduce the amount of
information it needs to store. This fact suggests an awkward
question: if there is a limited amount of information in the
object, why are we taking so many samples? Is there some
way to obtain measurements that automatically sieve out
the information in the object?
The original version of this paper appeared in Applied and
Computational Harmonic Analysis 26, 3 (2008), 301–321.