157
8
Compressive Sensing
8.1 Introduction
Compressed or compressive sensing (CS) is a mathematical theory of mea-
suring and retaining the most important part of the signal while sensing it.
It effectively performs dimensionality reduction of a signal in a linear man-
ner. It is one of the most exciting domains of modern times, and there is a
deluge of papers and research outcomes available to the researcher. It has
opened up new application vistas in the domains of computer science, elec-
trical engineering, applied mathematics, remote sensing, medical imaging,
communication, pattern recognition, and many more. Compressive sensing
is an interdisciplinary eld and draws its power from linear algebra, statis-
tics and random processes, signal processing, optimization, communication
theory, and space theory. This chapter is aimed at both the theorists and the
practitioners. It will be a review for novice practitioners who would be inter-
ested in peeping through the domain, and also act as a quick reference to the
theorist. This chapter will focus on the nite dimensional sparse signals and
will provide an overview of the basic theory underlying the ideas of com-
pressive sensing. Later in the chapter, we will discuss application based on
the compressive sensing theory covered in the former part. We will develop
a fragile domain watermarking application using CS. And nally, we present
a further line of investigation in this domain: exploiting signal and measure-
ment structure (i.e., use prior knowledge about the signal or physical process
to be sensed for further reduction in the sampling rate). For more tangible
discussions and simplicity, limited dimensional noncomplex signals are cov-
ered in this chapter.
8.2 Motivation for Compressive Sensing
This author has an eternal question in mind: Are the days of analog signal
processing over? This question has arisen due to the digital revolution we
are going through. Every walk of human as well as animal life has been
158 Image and Video Compression
touched by this revolution. Modern digital gadgets used by today’s toddlers
were only imagined in science ction half a century ago. But, thankfully the
consumer of this information to a very large extent remains Homo sapiens.
municating emotions using numbers instead of a language like Hindi). Thus,
a need for analog information and processing is going to prevail until the
time when human and machine are alike. At the same time, the digital revo-
lution is improving all walks of life. This essentially means that for getting
processing and then converted back to the analog domain for human con-
sumption. This human-centric conversion process is depicted in Figure8.1.
The digitization is realized by exploiting the limits of human perception.
But it is capable of providing nearly natural like signals to the human senses.
With the advancement of these technologies, the gap between real signals
and its digitally synthesized variants is minimizing. The terms hi- (high
delity), stereophonic, true pictures, and HDTV (high-denition television) are
now a part of daily life. Music players synthesize pure acoustics and three-
dimensional (3D) TVs are capable of producing real-like pictures. Billions
of bits are buzzing and running around us to make our life simpler and more
exciting. As seen in Figure8.1, the heart of this conversion process is analog-
form the front end and convert the analog real-world signal into the streams
of bits. These bits are then processed in the digital domain using software
algorithms running on digital signal processors. ADCs have to deal with a
wide range of analog input signals, and they have to sample these input sig-
nals. These samples are spaced in time and thus signal information between
them is lost. The sampling rate has to be fast enough so that an analog signal
can be regenerated from these samples. How fast this sampling rate should
be is answered by the fundamental Shannon-Whitakker-Nyquist theorem
(Shannon 1949).
Theorem 8.1 (Shannon 1949): An analog signal whose frequency is band
limited to B Hz, can be completely recovered from its samples which are
spaced at
B
1
2
seconds (secs) apart.
Analog
DAC