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 ( 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 T [ Uv ] T
+
and modify it to have instead:
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 ( M + N−c ) .
 
Search WWH ::




Custom Search