Digital Signal Processing Reference
In-Depth Information
Convergence and Performance Analysis of Oja's
Algorithm
Consider now Oja's algorithm (4.30) described in Subsection 4.5.1.
A difficulty arises in the study of the behavior of
W
(
k
) because the set of orthonormal
bases of the
r
-dominant subspace forms a
continuum
of attractors: the column vectors
of
W
(
k
) do not tend in general to the eigenvectors
u
1
,
...
,
u
r
, and we have no proof of
convergence of
W
(
k
) to a particular orthonormal basis of their span. Thus, considering
the asymptotic distribution of
W
(
k
) is meaningless. To solve this problem, in the same
way as Williams [78] did when he studied the stability of the estimated projection
matrix
P
(
k
)
¼
def
W
(
k
)
W
T
(
k
) in the dynamics induced by Oja's learning equation
dW
(
t
)
dt
¼
[
I
n
W
(
t
)
W
(
t
)
T
]
CW
(
t
), viz
dP
(
t
)
dt
¼
[
I
n
P
(
t
)]
CP
(
t
)
þP
(
t
)
C
[
I
n
P
(
t
)]
(4
:
78)
def
W
(
k
)
W
T
(
k
) whose dynamics are
we consider the trajectory of the matrix
P
(
k
)
¼
governed by the stochastic equation
P
(
k þ
1)
¼ P
(
k
)
þm
k
f
[
P
(
k
),
x
(
k
)
x
T
(
k
)]
þm
k
h
[
P
(
k
),
x
(
k
)
x
T
(
k
)]
(4
:
79)
def
(
I
n
P
)
CPC
(
I
n
P
). A
remarkable feature of (4.79) is that the field
f
and the complementary term
h
depend
only on
P
(
k
) and
not
on
W
(
k
). This fortunate circumstance makes it possible to
study the evolution of
P
(
k
) without determining the evolution of the underlying
matrix
W
(
k
). The characteristics of
P
(
k
) are indeed the most interesting since they
completely characterize the estimated subspace. Since (4.78) has a unique global
asymptotically stable point
P
¼ P
s
[69], we can conjecture from the stochastic
approximation theory [13, 44] that (4.79) converges almost surely to
P
. And conse-
quently the estimate
W
(
k
) given by (4.30) converges almost surely to the signal sub-
space in the meaning recalled in Subsection 4.2.4.
To evaluate the asymptotic distributions of the subspace projection matrix esti-
mator given by (4.79), we must adapt the results of Subsection 4.7.2 because the
parameter
P
(
k
) is here a
n n
rank-
r
symmetric matrix. Furthermore, we note that
some eigenvalues of the derivative of the mean field
f
(
P
)
¼
E[
f
(
P
,
x
(
k
)
x
T
(
k
))]
are positive real. To overcome this difficulty, let us now consider the following
parametrization of
P
(
k
) in a neighborhood of
P
introduced in [24, 25].
If {
u
ij
(
P
)
j
1
i j n
} are the coordinates of
P
2
P
in the orthonormal basis
(
S
i
,
j
)
1
ijn
defined by
def
with
f
(
P
,
C
)
¼
(
I
n
P
)
CPþPC
(
I
n
P
) and
h
(
P
,
C
)
¼
<
u
i
u
i
i ¼ j
u
i
u
j
þ
u
j
u
i
2
S
i
,
j
¼
:
p
i
,
j
def
Tr(
A
T
B
), then,
with the inner product under consideration is (
A
,
B
)
¼
P ¼ P
þ
X
1
i
,
jn
u
ij
(
P
)
S
i
,
j
Search WWH ::
Custom Search