Information Technology Reference
In-Depth Information
S
Z
must be decomposed into simpler parts that can be put in terms of eigende-
compositions
S
X
=
UΛU
T
(from the previous iteration) and
S
Y
=
VΔV
T
(that
can be done straightaway as
N
M
) along with their corresponding mean vec-
tors
x
j
and
y
j
. From the standard within-class scatter matrix definition we can
arrive at
S
Z
=
S
X
+
S
Y
+
SS
T
(2)
which could be seen as a generalization of the decomposition in [9]. In this
expression,
S∈
R
d×c
is a matrix whose columns are defined in terms of mean
as
M
j
N
j
vectors from
y
j
) for each class
j
.
To effectively arrive at a convenient eigendecomposition of
S
Z
, an orthonormal
basis, [
Uv
]
X
and
Y
(
M
j
+
N
j
)
(
x
j
−
∈
R
d×s
(where
s
is the rank of
S
Z
), spanning
S
and the centered
(that is, range spaces of
S
X
and
S
Y
) needs to be obtained. The
versions of
X
,
Y
∈
R
d×
(
s−r
)
is computed by using the residual operator with regard to
U
(as in Equation 1) of added subspaces (related to
unknown
v
Y
and
S
) and then applying
UU
T
V
)(
UU
T
S
GSO to the composite residual set [(
V
−
S−
)] (after removing
any zero vectors).
As [
Uv
] only differs from the sought
U
(in
S
Z
=
U
Λ
U
T
) in a rotation,
R
,
we can now write
S
X
+
S
Y
SS
T
=[
Uv
]
RΛ
R
T
[
Uv
]
T
+
and modify it to have instead:
RΛ
R
T
=
Λ
0
00
+
U
T
VΔV
T
UU
T
VΔV
T
v
v
T
VΔV
T
Uv
T
VΔV
T
v
+
U
T
SS
T
UU
T
SS
T
v
v
T
SS
T
Uv
T
SS
T
v
which constitutes a new eigenproblem that allows us to compute
R
and corre-
spondingly
U
=[
Uv
]
R
.
The above computation needs
O
(
(
N
3
+
s
3
)+
d
(
N
2
+
s
2
)) time and dom-
inates the cost of the whole incremental algorithm that will be referred to as
IDCV-EVD. This constitutes an improvement with respect to the correspond-
ing basic algorithm which would imply a computation time in
O
(
(
M
+
N
)
3
+
d
(
M
+
N
)
2
). Note that the benefit will be higher if the rank of the overall scatter
matrix,
s
, is reduced. This can be easily done by neglecting small eigenvalues in
the EVD decompositions used.
3.2
Incremental DCV through GSO
An incremental version of the GSO-based DCV is also possible by constructing
B
Y
∈
R
d×N
, the difference vectors in
Y
with regard to the
same
samples as
B
X
,
namely as
y
j
−
x
1
j
,with
j
=1
, .., c
,and
k
=1
, .., N
j
.
In this case, GSO can be applied to
B
Y
starting with the orthonormal ba-
sis previously computed for
B
X
,
Θ
, to add new vectors to complete an incre-
mented orthonormal basis,
Θ
, that spans the whole difference set, [
B
X
B
Y
]
∈
R
d×
(
M
+
N−c
)
.
Search WWH ::
Custom Search