Digital Signal Processing Reference
In-Depth Information
2
))
in the preceding algorithm is suffi-
cient but not necessary for the algorithm to converge (the upper bound could actually
be
2
2
Remark 1
The condition
μ
t
∈
(0
,
2
/
(
|||
H
|||
|||
|||
2
). Other variants of this algorithm have been proposed very recently in the
literature to accelerate the forward-backward algorithm for solving
(
P
λ
)
. These meth-
ods basically propose different strategies to choose the descent step-size sequence
(
/
|||
H
|||
μ
t
)
t
to get faster practical convergence behavior; see, for example, Elad (2006), Vonesch
and Unser (2007), and Wright et al. (2009). These algorithms can all be seen as spe-
cial instances of a more general forward-backward splitting considered by Chen and
Rockafellar (1997) (see also references therein), where
μ
t
may actually be a matrix.
Accelerated Multistep Algorithm
In the same vein as in Section 7.3.2.3, the convergence rate on the objective (7.26)
can be improved to
O
(1
t
2
) using the accelerated multistep Nesterov algorithm
(Nesterov 2007). Indeed, problem (
P
λ
) satisfies the necessary requirements on
F
1
and
F
2
to apply the Nesterov iteration. Unlike Algorithm 22, the Nesterov acceler-
ated version uses explicitly all previous iterates
/
(
t
)
, hence the
name “multistep algorithm.” Algorithm 23 details the steps of the Nesterov scheme
to minimize (
P
λ
). It is formulated using proximal operators, as described by Weiss
et al. (2009).
(
k
)
,
k
α
<
t
to compute
α
Algorithm 23
Nesterov Scheme to Solve (
P
λ
)
(0)
T
,
2
2
)),
(0)
Initialization:
Choose some
α
∈ R
μ
∈
(0
,
2
/
(
|||
H
|||
|||
|||
θ
0
=
0,
ξ
=
0.
Main iteration:
for
t
=
0
to
N
iter
−
1
do
1.
First proximal computation:
(
t
)
(0)
(
t
)
)
υ
=
prox
(
α
−
ξ
.
(7.29)
θ
t
μθ
t
(
t
)
(
t
)
(
t
)
=
θ
t
α
+
a
t
υ
2. Set
a
t
=
μ
+
μ
2
+
4
/
2 and
ω
.
θ
t
+
a
t
3.
Second proximal computation:
+
2
∗
H
∗
y
(
t
)
)
(
t
+
1)
(
t
)
α
=
prox
ω
−
H
(
ω
.
(7.30)
μ/
2
4.
Accumulate the gradient directions:
a
t
∗
H
∗
y
1)
)
(
t
+
1)
(
t
)
(
t
+
ξ
=
ξ
−
−
H
(
α
.
(7.31)
5. Update the step
θ
t
+
1
=
θ
t
+
a
t
.
(
N
iter
)
.
Output:
Solution of (
P
λ
):
α
It worth noting that Beck and Teboulle (2009), building on another paper by
Nesterov, have proposed an accelerated algorithm to solve (
P
λ
) that achieves the
same global rate of convergence as Algorithm 23. Despite some similarities, the
