Digital Signal Processing Reference
In-Depth Information
Table 11.1.
Computation Times in Seconds for Exact CS Reconstruction from
Hadamard Measurements
2
8
2
9
2
10
2
11
2
12
2
13
2
14
m
DR
0.58
1.17
2.52
3.80
6.43
15.18
36.20
LARS
0.28
1.00
3.65
6.60
10.54
24.77
59.38
LP-IP
2.07
9.85
45.35
163.62
631.57
3191.38
13175.63
StOMP
0.34
0.84
2.36
3.61
6.38
16.65
43.13
Note:
The tests were run under MATLAB with an Intel Xeon Core Duo 3 GHz, 8 GB RAM.
The script
in the toolbox that reproduces the following experiment
is
. We solve BP equation (7.3) using DR splitting
1D/Demos/testsCS1times.m
Algorithm 26;
H
is a
m
×
N
,
N
=
4
m
, random sensing matrix generated from the
Hadamard and Fourier ensembles,
=
I
(canonical basis). The support of
α
was
selected uniformly at random with sparsity level 0
05
m
and normally distributed
nonzero entries. Besides Algorithm 26, three other algorithms are compared: the
least angle regression (LARS)/Lasso (Tibshirani 1996; Efron et al. 2004), linear pro-
gramming with interior point solver (LP-IP) (Chen et al. 1999), and Stage-wise Or-
thogonal Matching Pursuit (StOMP) (Donoho et al. 2006b). The results are shown
in Table 11.1 (similar results were observed for Fourier measurements). The DR
splitting solver is among the fastest and becomes faster than the other algorithms as
m
gets large.
Figure 11.4 depicts the images recovered from 17 percent noiseless and noisy
(SNR = 30 dB) Fourier measurements of the
N
.
256
2
“Mondrian” painting im-
=
age. The dictionary
is a tight
frame. In the noiseless case, the BP problem was again solved with Algorithm 26. In
the noisy case, the radius of the
is the orthogonal wavelet transform, and hence
H
2
constraint in
Algorithm 27 to solve equation (7.5)
1
2
2
σ
=
√
m
(i.e., (
P
2
σ
m
, as advocated in Section 7.4.2.5. For
Algorithm 24 for solving equation (7.4), the choice of the regularization parameter
was done on a trial-test basis. The results can be reproduced by running the script
2D/Demos/testsCS2DimplicitEx2.m
)) was set to
σ
ε
+
/
.
11.9 SUMMARY
In this chapter, we overviewed the essential ingredients of the compressed sens-
ing theory as a paradigm for jointly sampling and compressing signals known to
be sparse in some dictionary. By establishing a direct link between sampling and
sparsity, compressed sensing is now beginning to have a huge impact in many scien-
tific fields. We then discussed the recovery problem in compressed sensing, which is
viewed as a linear inverse problem in which the sparsity penalty is the
1
norm, and
we gave sufficient conditions under which
1
minimization succeeds. We have seen
that CS could offer an elegant solution to the Herschel data transfer problem and
constitutes one of the world's premier applications of CS to real space science data.
Compressed sensing is currently one of the most active research areas in applied
mathematics and signal processing. Despite the huge amount of work being pub-
lished, many important questions remain to be investigated more deeply. Among
