1
Compressed Sensing and Sparse Signal Processing
Wu-Sheng Lu
University of Victoria, Canada
November 2010
2
List of Contents
I. Digital Signals: Sampling and Representation ……………………………………….. .. 3
1.1 The Shannon-Nyquist Sampling Theorem ………………………………………………… 3
1.2 Sparse and Compressible Signals ………………………………………………………….. 8
II. Compressed Sensing and Signal Reconstruction ……………………………………….21
2.1 Sensing a Sparse Signal ……………………………………………………………………21
2.2 Compressed Sensing for Noisy Data ……………………………………………………....28
III. Some Inverse Problems in Image Processing ………………………………………….. 33
3.1 Proximal-Gradient Methods for Convex Optimization Problems …………………………33
3.2 Fast Gradient Projection Algorithms for Constrained TV-Based Image De-Noising …….. 42
3.3 A Gradient Projection Algorithm for Constrained TV-Based Image De-Blurring ………51
References ………………………………………………………………………………………...56
3
I. Digital Signals: Sampling and Representation
1.1 The Shannon-Nyquist Sampling Theorem
The Shannon-Nyquist Sampling Theorem:
A continuous-time signal x(t) with frequencies no higher than f
max
(in Hz) can be reconstructed from
its samples x[k] = x(kT
s
), if the samples are taken at a rate f
s
= 1/T
s
that is greater than 2 f
max
.
The frequency 2 f
max
is called the Nyquist rate. Obviously, the above theorem can be stated as:
A continuous-time signal x(t) with frequencies no higher than f
max
(in Hz) can be reconstructed from
its samples x[k] = x(kT
s
), if the samples are taken at the Nyquist rate.
There are several ways to explain this important theorem. In what follows, we present a
graphics-based explanation and an analytic explanation of the theorem.
A. A Graphics-Based Explanation
The explanation here is given in the frequency domain by examining the spectrum of the sampled
signal in relation to that of the original continuous-time signal.
An analog signal is said to be band-limited, if it has an identifiable maximum frequency in its
spectrum, say, f
max
Hz. Obviously, the signal x(t) in Shannon’s theorem is band-limited.
There are great many real-world signals that are band-limited. For example, speech and music are
always band-limited. To process signals that are not band-limited, it is often of convenience to deal
with their band-limited counterparts by lowpass or bandpass filtering the signals as a pre-processing
step. This step is often an integral part of a DSP system. In Fig. 1.1, this step is the first function
block, and the filter that turns the input signal into a band-limited signal is called anti-aliasing filter.
Without the loss of generality, let us now consider a band-limited continuous-time signal x(t) whose
spectrum is within the region
max
0 ≤Ω≤Ω where
max max
2
f
π
Ω
= . Suppose signal x(t) is defined for
t−∞< < ∞
and is sampled uniformly at t = nT
s
, where T
s
= 1/ f
s
denotes the sampling period in
seconds (this means that f
s
is the sampling frequency) and n
−
∞< <∞are integers. The diagram in
Fig. 2.4 describes this ideal sampling model.
x(t)
x
s
(t)
x
s
(t)
x(t)
s(t)
s(t)
tt
t
Figure 1.1
In Fig. 1.1, s(t) is the periodic impulse train
() ( )
s
k
s
ttkT
δ
∞
=−∞
=−
∑
4
where
()t
δ
is the unit impulse function, and the sampled signal is obtained by modulating s(t) with
x(t) as
() ()() () ( )
s
s
k
x
txtstxt tkT
δ
∞
=−∞
== −
∑
(1.1)
which gives
() ( ) ( )
s
ss
k
x
txkTtkT
δ
∞
=−∞
=−
∑
(1.2)
The sampling process is described in Fig. 1.1 and can be analyzed in the frequency domain as
follows. Applying Fourier transform to (1.1) and note that the Fourier transform of a product of two
functions is equal to the convolution of the Fourier transforms of these functions, i.e.,
1
() ()()
2
s
Xj Xj Sj
π
Ω
=Ω∗Ω
By applying the Fourier-series kernel theorem, we obtain
2
() ( )
s
k
s
Sj k
T
π
δ
∞
=−∞
Ω
=Ω−Ω
∑
where
2/
s
s
T
π
Ω=
is the angular sampling frequency in radians/sec. Therefore,
1
() (( ))
ss
k
s
Xj Xj k
T
∞
=−∞
Ω
=Ω−Ω
∑
(1.3)
Equation (1.3) is important because it relates explicitly the spectrum of the sampled analog signal x
s
(t)
to that of the original analog signal x(t). We see that the Fourier transform of x
s
(t) consists of
periodically repeated copies of the Fourier transform of x(t). More specifically, Eq. (1.3) says that the
copies of
()XjΩ are shifted by integer multiples of the sampling frequency and then superimposed
to generate the periodic Fourier transform of the impulse train of samples. Two representative cases
in terms of the value of
max
Ω compared with that of
maxs
Ω
−Ω are shown in Figs. 1.2 and 1.4.
Case I: The sampling frequency is sufficiently high such that
max maxs
Ω−Ω >Ω i.e.,
max
2
s
Ω
>Ω (1.4)
In this case, the replicas of ( )XjΩ do not overlap, see Fig. 1.2c. Consequently, the continuous-time
signal x(t) can be recovered by ideal lowpass filtering as illustrated in Fig. 1.3.
5
Ω
S
X(jΩ)
S(jΩ)
0
−Ω
max
Ω
max
0
X(j(Ω−kΩ
S
))
−Ω
S
X
S
(jΩ)
(a)
(b)
Ω
S
(c)
−Ω
S
0
Ω
S
(d)
−Ω
max
Ω
max
Ω
S
−Ω
max
0
−Ω
S
. . . . . .
.
. . . . .
k = -1
k = 0 k = 1
Figure 1.2
