DOI:10.1145/1859204.1859229
dECEm BEr 2010 | v ol. 53 | No. 1 2 | COM MUN ICATIO NS OF TH E A CM 93
CoSaMP: Iterative Signal
Recovery from Incomplete
and Inaccurate Samples
By Deanna Needell and Joel A. Tropp
Abstract
Compressive sampling (CoSa) is a new paradigm for devel-
oping data sampling technologies. It is based on the prin-
ciple 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 pre-
serves 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. WHAT IS COMPRESSIVE SAMPLING?
In many applications, the ambient dimension of a data vec-
tor does not reflect the actual number of degrees of free-
dom 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 compress-
ible 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 cod-
ers 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?
One way to exploit the gap between nominal dimen-
sion and degrees of freedom is to perform dimension
reduction. This idea has a long tradition in computer
science. Indeed, to solve geometric problems involving
high-dimensional data, we often map the data to a lower
dimension while approximately preserving the geometric
properties that are relevant to the computation. One stan-
dard method for achieving this goal is to use a random
projection to the data.
The main idea in compressive sampling (CoSa) is to
develop sampling technologies based on dimension reduc-
tion. The mathematical foundation for this approach is the
fact that an appropriate random projection of a compress-
ible signal retains most of the information in that signal.
The coordinates of this randomly projected signal are inter-
preted as samples, and the number of samples we need
is comparable with the information content of the object
we are sampling. Because we have a lot of flexibility when
designing projections, we have flexibility in engineering the
sampling hardware.
An intriguing example of a CoSa sensing device is the
Rice University single-pixel camera. This camera uses a digi-
tal micromirror device (DMD) to selectively black out a ran-
dom subset of pixels from an image and to measure the total
intensity of the remaining pixels. By applying many random
masks in sequence, we obtain a collection of samples that
captures the information in the image.
Another key fact about CoSa is that we cannot use
simple linear techniques to reconstruct the data vector
from the random samples. Instead, we must develop
more sophisticated algorithms. One approach that has
received a lot of attention is convex programming based
on l
1
minimization. This abstract describes an algo-
rithm, called CoSaMP, that is based on the greedy pursuit
schema.
18, 19
CoSaMP was the first computational tech-
nique that provably achieved near-optimal guarantees
on resource usage. Using the techniques from our paper,
researchers later demonstrated that other algorithms
offer comparable performance guarantees. Another algo-
rithm similar to CoSaMP, called Subspace Pursuit,
9
was
published at the same time, but the accompanying analy-
sis was less complete.
The original version of this paper appeared in Applied and
Computational Harmonic Analysis 26, 3 (2008), 301–321.
评论1