Digital Signal Processing Reference
In-Depth Information
In fact, the proximal FB splitting recursion (7.24) can be generalized to deal with
nonconvex penalties
and still has convenient convergence properties (Bredies and
Lorenz 2009). For instance, consider the case of
p
regularization for 0
<
p
<
1,
α
[
i
]
=
λ
i
∈I
p
:
p
p
(
α
)
=
λ
α
1
2
2
p
p
+
λ
α
min
α
∈R
y
−
H
α
.
(7.67)
T
Define the iterative thresholding procedure
∗
H
∗
y
(
t
)
(
t
+
1)
(
t
)
α
=
α
+
μ
t
−
α
,
prox
H
(7.68)
p
μ
t
λ
·
2
) and the proximity operator is separable in each coordi-
where
μ
t
∈
(0
,
1
/
(
|||
H
|||
nate. Even if the
p
penalty is now nonconvex, it was shown that its proximity op-
erator has a unique closed form solution given by (Antoniadis and Fan 2001; Fadili
and Bullmore 2005; Fadili et al. 2009c)
0
if
α
[
i
]
≤
μλτ
p
α
˜
[
i
]
=
prox
p
(
α
[
i
])
=
[
i
])
˜
[
i
]
if
α
[
i
]
>μλτ
;
−
μλ
|·|
p
1
α
−
μλ
α
α
[
i
]
p
sign( ˜
p
(7.69)
[
i
]
>μλτ
p
, equation (7.69) has a shrinkage
amount sandwiched between soft and hard thresholding. Bredies and Lorenz (2009)
have shown subsequent convergence of equation (7.68) to a stationary point that
satisfies necessary conditions of a global minimizer. See Bredies and Lorenz (2009)
for finer convergence results that depend on the structure of
F
p
)
μλ
p
)
p
−
1
p
.For
α
1
τ
p
=
(2
−
p
(1
−
2
−
.
As the sparsity penalties are no longer convex, continuation and warm start by
a decreasing threshold is even more crucial than in IST to ensure robustness to ini-
tialization and local minima. In compressed sensing recovery, IHT was reported to
perform better than IST (Donoho and Maleki 2009). This is not necessarily true for
other inverse problems. In the next two chapters, hard thresholding will be at the
heart of the iterative stagewise pursuit algorithms that we will develop.
=
H
7.8 GUIDED NUMERICAL EXPERIMENTS
The splitting framework described in this chapter has been applied to solve several
inverse problems such as signal decomposition, sparse spike deconvolution, and re-
covery in compressed sensing. A MATLAB toolbox is made available freely un-
der the CeCILL license for download (http://www.SparseSignalRecipes.info). This
toolbox is a collection of MATLAB functions and scripts implementing the algo-
rithms discussed in this chapter and reproducing the guided numerical experiments
described later. It has the same structure as the MCALab toolbox discussed in
Section 8.8.1.
7.8.1 Sparse Decomposition
The results of this experiment can be reproduced with the script
1D/Demos/
of the toolbox. The splitting algorithms are applied to a sparse
decomposition problem of a 1-D signal of
N
testsApprox1DEx7.m
I
). The signal is
a superposition of two chirps (i.e., two frequency-modulated sines) and corrupted
=
1024 samples (
H
=
