Digital Signal Processing Reference
In-Depth Information
A complete proof is given by Fadili and Starck (2009) using Fenchel-Rockafellar
duality, the forward-backward scheme to be discussed in Section 7.3.3.2, as well as
the rules in Section 7.3.2.1 and equation (7.11). Note that the case of tight frames
was proved differently by Combettes and Pesquet (2007a).
When
F
corresponds to a frame, the convergence rate (7.19) of the one-step
forward-backward (FB) iteration depends clearly on the redundancy of the frame.
The higher the redundancy, the slower the convergence. More precisely, the num-
ber of necessary iterations to obtain a solution up to the accuracy
on the iterates is
O
(
c
c
1
−
1
). For the general case (3), where
F
is not a frame, the convergence rate
to the proximity operator is only
O
(1
log
/
t
) (Fadili and Starck 2009), hence necessitat-
ing as large as
O
(1
/
) iterations to reach an
convergence tolerance.
Accelerated Multistep Algorithm
Instead of Algorithm 20, cases (2) and (3) of Section 7.3.2.3 can be solved using a
multistep method inspired from the work of Nesterov (2005, 2007). The multistep
scheme to be used instead of Algorithm 20 is summarized in Algorithm 21. If
F
is a
not a frame, Algorithm 21 applies with
c
1
=
0.
Algorithm 21
Nesterov Scheme to Compute the Proximity Operator of Precompo-
sition with an Affine Operator
Initialization:
u
(0)
dom(
F
∗
),
(0)
∈
θ
0
=
0,
ξ
=
0,
μ
∈
(0
,
2
/
c
2
).
Main iteration:
for
t
=
0
to
N
iter
−
1
do
1. Set
c
1
θ
t
).
2. First proximal computation:
ρ
t
=
μ
(1
+
prox
F
/θ
t
(
u
(0)
/θ
t
=
θ
t
I
(
t
)
(
t
)
)
υ
−
−
ξ
.
ρ
t
θ
t
=
θ
t
u
(
t
)
+
a
t
υ
(
t
)
t
(
t
)
3. Set
a
t
=
ρ
t
+
ρ
+
4
/
2 and
ω
.
θ
t
+
a
t
4. Second proximal computation:
prox
2
μ
−
1
F
2
F
(
t
)
y
2
I
u
(
t
+
1)
μ
−
1
(
t
)
F
∗
ω
=
μ/
−
ω
+
α
−
−
,
a
t
F
y
(
t
+
1)
(
t
)
F
∗
u
(
t
)
ξ
=
ξ
−
α
−
−
.
θ
t
+
1
=
θ
t
+
5. Update
a
t
.
F
∗
u
(
N
iter
)
.
Output:
Proximity operator of
F
◦
A
at
α
:
α
−
This algorithm enjoys the following convergence rates; see Fadili and Starck
(2009) for a proof. Suppose that
c
2
). Let
u
(0)
dom(
F
∗
), and define
μ
∈
(0
,
2
/
∈
u
−
u
(0)
, where
u
is the optimal dual solution. If
F
is a frame (nontight),
R
=
then
∀
t
≥
1
2
c
2
R
2
1
c
1
8
c
2
−
2(
t
−
1)
)
2
p
(
t
)
−
prox
F
◦
A
(
α
≤
+
;
(7.21)
