Compressive Sensing - Sparse Representations and Compressive Sensing for Imaging and Vision - page 15

2.6 Numerical Examples

We end this section by considering the following two examples. In the first example,
a 1D signal x of length 200 with only 10 nonzero elements is undersampled using
a random Gaussian matrix

200 as shown in Fig. 2.3 (a). Here, the
sparsifying transform B is simply the identity matrix and the observation vector y is
of length 50. Having observed y and knowing A

Φ of size 50 ×

= Φ the signal x is then recovered

by solving the following optimization problem

x 1 subject to y Ax .

x = arg min

x ∈ R

N

= (2.15)

As can be seen from Fig. 2.3 (d), indeed the solution to the above optimization
problem recovers the sparse signal exactly from highly undersampled observations.
Whereas, the minimum norm solution (i.e. by minimizing the

2 norm), as shown in
Fig. 2.3 (e), fails to recover the sparse signal. The errors corresponding the 1 and 2

recovery are shown in Fig. 2.3 (f) and Fig. 2.3 (g), respectively.
In the second example, we reconstructed an undersampled Shepp-Logan phan-
tom image of size 128 128 in the presence of additive white Gaussian noise

with signal-to-noise ratio of 30 dB. For this example, we used only 15% of the
random Fourier measurements and Haar wavelets as a sparsifying transform. So
the observations can be written as y

×

are
the noisy compressive measurements, the restriction operator, Fourier transform
operator, the Haar transform operator, the sparse coefficient vector and the noise
vector with

= MFB α + η ,where y , M , F , B , α and η

η 2 ≤ ε , respectively. The image was reconstructed via α estimated

by solving the following optimization problem

α α 1 subject to

α ≤ ε . α = ˆ arg min y − MFB

The reconstruction from 1 minimization is shown in Fig. 2.4 (d) and

Fig. 2.3 (e), respectively. This example shows that, it is possible to obtain a stable
reconstruction from the compressive measurements in the presence of noise. For
both of the above examples we used SPGL1 [8] algorithm for solving the

2 and

1

minimization problems.
In [23], [47], a theoretical bound on the number of samples that need to be
measured for a good reconstruction has been derived. However, it has been observed
by many researchers [79], [22], [142], [19], [26] that in practice samples in the
order of two to five times the number of sparse coefficients suffice for a good
reconstruction. Our experiments also support this claim.