Digital Signal Processing Reference
In-Depth Information
In general, for general implicit operator
F
, the preceding projector can be computed
using a conjugate gradient solver. This expression, however, simplifies greatly when
F
is a tight frame, that is,
FF
∗
=
c
I
.
The steps to solve (
P
q
) (7.26) are summarized in Algorithm 25, where the prox-
σ
imity operator of
is computed thanks to the results of Section 7.3.2.2.
q
σ
(
t
)
(
t
+
1
/
2)
(
t
)
, and there is no need to
Remark 2
It is obvious that if
α
∈ C
, then
α
=
α
compute the projection in the first proximal step.
Algorithm 25
Douglas-Rachford Splitting to Solve (
P
q
)
σ
(0)
T
,
Initialization:
Choose some
α
∈ R
μ
∈
(0
,
2),
γ>
0, and
σ
≥
0.
Main iteration:
for
t
=
0
to
N
iter
−
1
do
(
t
)
). For
1.
Projection step:
If
σ
=
0, apply equation (7.42) to compute
P
C
0
(
α
q
σ>
is a tight frame, apply equation (7.17); otherwise, apply Algo-
rithm 20 or Algorithm 21 to compute
0, if
H
(
t
)
) using the appropriate pro-
P
C
(
α
q
σ
jector onto
B
p
, as discussed earlier. Compute
σ
(
t
+
1
/
2)
(
t
)
)
(
t
)
α
=
2
P
C
(
α
−
α
.
(7.43)
q
σ
2.
Proximal step:
2
2prox
γ
(
t
+
1
/
2)
(
t
+
1
/
2)
(
t
+
1)
(
t
)
α
=
(1
−
μ/
2)
α
+
μ/
α
−
α
.
(7.44)
Output:
Solution of (
P
q
(
N
iter
)
).
):
P
C
(
α
q
σ
σ
7.4.2.2 Computational Complexity
When
F
corresponds to a tight frame and the projector onto
B
q
can be com-
puted analytically, the computational complexity of each iteration of Algorithm 25
is dominated by that of applying
H
,
=
H
σ
, and their adjoints. See Section 7.4.1.2 for
typical examples of their cost. For a general
F
, the projector
is computed via a
nested inner iteration using either Algorithm 20 or Algorithm 21. In practice, these
projection algorithms are run a finite number of inner iterations
N
t
at each outer
iteration
t
. Each outer iteration
t
then costs
N
t
×
P
C
q
σ
(complexity of
H
and
H
∗
+
com-
∗
). The next section gives some guidelines on how to choose the
number of inner iterations
N
t
for Algorithm 25 to converge.
plexity of
and
7.4.2.3 On the Number of Inner Iterations
At each iteration
t
, after
N
t
inner iterations to compute an estimate
P
C
(
t
)
)ofthe
(
α
q
σ
(
t
)
), we have an error term
e
t
such that
P
C
projector
P
C
(
α
q
σ
(
t
)
)
(
t
)
)
(
α
= P
C
(
α
+
e
t
.
(7.45)
q
σ
q
σ
For the DR Algorithm 25 to converge with
μ
∈
(0
,
2), the error sequence
e
t
must
obey
t
∈N
e
t
<
+∞
(Combettes 2004). In view of the convergence rates in
