Digital Signal Processing Reference
In-Depth Information
in the literature to the complex domain such that the limitations of the Newton method
can be mitigated.
Linear Conjugate Gradient (CG) Updates
For the Newton's method
given in (1.3.1), in order to achieve convergence, we require the search direction
D w
R
to be a descent direction when minimizing a given cost function. This is the case
2
f
@ w
R
@ w
R
@
when the Hessian
is positive definite. However, when the Hessian is not
positive definite,
D w
R
may be an ascent direction. The line search Newton-CG
method is one of the strategies for ensuring that the update is of good quality.
In this strategy, we solve (1.30) using the CG method, terminating the updates
D w
R
0.
2
f
@ w
R
@ w
R
@
if
D w
R
N
. Hence, writing it in the
form
f
(
w
,
w
) is much more straightforward than converting it to a function of the
2
N
dimensional real variable as in
f
(
w
R
). Using a procedure similar to the derivation
of complex gradient and Newton updates, the complex-valued CG updates can be
derived using the real-valued version given in Section 1.3.1. Using (1.25) and
(1.26), and defining
s
W
@f =@w
, the complex CG method can be derived as:
In general, a complex-valued function is defined in
C
Complex Conjugate Gradient Updates
Given an initial gradient
s
(0);
Set
x
(0) =
0
,
c
(0) =
2
s
(0), k = 0;
while j
s(k)
j
=
0
s
H
(
k
)
s
(
k
)
Re{
c
T
(
k
)
H
2
c
(
k
)
þc
T
(
k
)
H
1
c
(
k
)}
;
x
(
k þ
1)
¼ x
(
k
)
þa
(
k
)
c
(
k
)
;
s
(
k þ
1)
¼ s
(
k
)
þa
(
k
)(
H
2
c
(
k
)
þH
1
c
(
k
))
;
a
(
k
)
¼
s
H
(
k
þ
1)
s
(
k
þ
1)
s
H
(
k
)
s
(
k
)
b
(
k þ
1)
¼
;
c
(
k þ
1)
¼s
(
k þ
1)
þb
(
k þ
1)
c
(
k
)
;
k ¼ k þ
1
;
end(while)
where
H
1
and
H
2
is defined in (1.32).
The complex line search Newton-CG algorithm is given as:
for k
= 0,1,2,
...
Compute a search direction
Dw
by applying the
complex CG update rule, starting at
x
(0)= 0.
Terminate when Re{
c
T
(
k
)
H
2
c
(
k
)
þc
T
(
k
)
H
1
c
(
k
)}
0
;
Set
w
(k + 1)=
w
(
k
)+
mDw
,where
m
satisfies a complex
Wolfe condition.
end
Search WWH ::
Custom Search