2 Chapter 1. Introduction to Compressed Sensing
images, videos, and other data can be exactly recovered from a set of uniformly
spaced samples taken at the so-called Nyquist rate of twice the highest frequency
present in the signal of interest. Capitalizing on this discovery, much of signal
processing has moved from the analog to the digital domain and ridden the wave
of Moore’s law. Digitization has enabled the creation of sensing and processing
systems that are more robust, flexible, cheaper and, consequently, more widely
used than their analog counterparts.
As a result of this success, the amount of data generated by sensing systems
has grown from a trickle to a torrent. Unfortunately, in many important and
emerging applications, the resulting Nyquist rate is so high that we end up with
far too many samples. Alternatively, it may simply be too costly, or even physi-
cally impossible, to build devices capable of acquiring samples at the necessary
rate [146, 241]. Thus, despite extraordinary advances in computational power, the
acquisition and processing of signals in application areas such as imaging, video,
medical imaging, remote surveillance, spectroscopy, and genomic data analysis
continues to pose a tremendous challenge.
To address the logistical and computational challenges involved in dealing
with such high-dimensional data, we often depend on compression, which aims
at finding the most concise representation of a signal that is able to achieve
a target level of acceptable distortion. One of the most popular techniques for
signal compression is known as transform coding, and typically relies on finding
a basis or frame that provides sparse or compressible representations for signals
in a class of interest [31, 77, 106]. By a sparse representation, we mean that for
a signal of length n, we can represent it with k n nonzero coefficients; by a
compressible representation, we mean that the signal is well-approximated by
a signal with only k nonzero coefficients. Both sparse and compressible signals
can be represented with high fidelity by preserving only the values and locations
of the largest coefficients of the signal. This process is called sparse approxima-
tion, and forms the foundation of transform coding schemes that exploit signal
sparsity and compressibility, including the JPEG, JPEG2000, MPEG, and MP3
standards.
Leveraging the concept of transform coding, compressed sensing (CS) has
emerged as a new framework for signal acquisition and sensor design. CS enables
a potentially large reduction in the sampling and computation costs for sensing
signals that have a sparse or compressible representation. While the Nyquist-
Shannon sampling theorem states that a certain minimum number of samples
is required in order to perfectly capture an arbitrary bandlimited signal, when
the signal is sparse in a known basis we can vastly reduce the number of mea-
surements that need to be stored. Consequently, when sensing sparse signals we
might be able to do better than suggested by classical results. This is the fun-
damental idea behind CS: rather than first sampling at a high rate and then
compressing the sampled data, we would like to find ways to directly sense the
data in a compressed form — i.e., at a lower sampling rate. The field of CS grew
out of the work of Cand`es, Romberg, and Tao and of Donoho, who showed that
- 1
- 2
- 3
- 4
- 5
- 6
前往页