Digital Signal Processing Reference
In-Depth Information
6
Sparsity and Noise Removal
6.1 INTRODUCTION
In this chapter, we are interested in recovering
X
of
N
equally spaced samples ac-
quired on a regular
d
-dimensional grid (
d
=
1 for one-dimensional (1-D) signals and
d
=
2 for 2-D images), from its noisy measurements
Y
:
Y
[
k
]
=
X
[
k
]
ε
[
k
]
k
=
1
,...,
N
,
(6.1)
where
ε
is the contaminating noise and
is any composition of two arguments
(e.g.,
for multiplicative noise). This ill-posed problem is
known as denoising, and is a long-standing problem in signal and image process-
ing. Denoising can be efficiently attacked under the umbrella of sparse represen-
tations. Indeed, if the sought after signal is known to be sparse (or compressible)
in some transform domain (such as those discussed in the previous chapters), it is
legitimate to assume that essentially only a few large coefficients will contain infor-
mation about the underlying signal, while small values can be attributed to the noise
that contaminates all transform coefficients. The classical modus operandi is to first
apply the transform analysis operator (denoted
T
) to the noisy data
Y
, then to apply
a nonlinear estimation rule
+
for additive noise,
×
D
to the coefficients (each coefficient individually or as
a group of coefficients), and finally, to compute the inverse transform (denoted
R
)
to get an estimate
X
.Inbrief,
X
=
R
D
(
T
Y
)
.
(6.2)
This approach has already proven to be very successful on both practical and the-
oretical sides (Starck and Murtagh 2006; Hardle et al. 1998; Johnstone 1999, 2002).
In particular, it is well established that the quality of the estimation is closely linked
to the sparsity of the sequence of coefficients representing
X
in the transform do-
main. To make this precise, suppose that the noise in equation (6.1) is additive white
Gaussian with variance
2
, that is,
2
)
σ
ε
[
k
]
∼N
(0
,σ
,
∀
k
. Assume also that the trans-
form corresponds to an orthonormal basis, and
is the hard thresholding operator
(see equation (6.12)). Donoho and Johnstone (1994) have shown that if the
m
-term
D
119
