**3.3 Datasets**

**4.1.1 Addition of Data Samples**

The incremental formulation of MvIDDA has four different cases depending on the nature of an incoming data stream and the class labels of new data samples.

• **Sequential increment and Existing class**- To be used when only one new sample is added
at a time and it belongs to one of the already existing classes (Refer fig. 4.1a).

• **Sequential increment and New class**- To be used when only one new sample is added at
a time and it belongs to a new class (Refer fig. 4.1b).

(a) Sequential Increment and Existing Class (b) Sequential Increment and New Class

(c) Chunk Increment and Existing Class (d) Chunk Increment and New Class

Figure 4.1: Cases of Increment: (a) A new data sample is added to every view. It belongs to an existing class. (b) A new data sample is added to every view. It belongs to a new class. (c) A chunk of new data samples is added. None of the new data samples belong to a new class. (d) A chunk of new data samples is added. Some of the new data samples belong to a new class.

• **Chunk increment and Existing class**- To be used when a group of new samples is added
at a time and none of the new samples belongs to a new class (Refer fig. 4.1c).

• **Chunk increment and New class**- To be used when a group of new samples is added at
a time and some of the new samples belong to new classes (Refer fig. 4.1d).

Each of the four cases of MvIDDA follows four steps that incrementally update- (i) number of data samples, (ii) means, (iii) within-class scatter matrix, and (iv) between-class scatter matrix, respectively. Once these entities are updated, the new scatter matrices are used to find optimal projection vectors using Eq.(2.5). Algorithm 1 presents the workings of incremental MvIDDA.

**4.1.1.1 Sequential Increment and Existing Class**

Let us suppose only one data sample is added to the base set at a time and it belongs to an already
existing class *E*. Let us denote this data sample by ¯X = {¯**x***j*|*j* = 1*,*· · · *, v*} and ¯**x***j* ∈ R^{p}^{j}. Let
Y¯ ={**y**¯_{j} =**W**^{T}_{j}**x**¯*j*|*j*= 1*,*· · · *, v*} be the projection of ¯X onto the common discriminant space.

**A) Updating the number of data samples-** As the class already exists in C, we have to
update the number of total data samples (*n*), the number of data samples in class *E* (*n**E*), and
the number of data samples per class per view of class *E* (*n**Ej*). Here, *n**ij* and *n**i* for other classes
*i*∈ C − {*E*} do not change.

*n*^{0}_{Ej} =*n*_{Ej}+ 1*, n*^{0}_{E} =*n*_{E}+*v* and *n*^{0}=*n*+*v*

**B) Updating the means-** As the new data sample has been added to class *E*, we update the
means per class per view (**m***Ej*(*x*)) and class mean (**m***E*) of class*E*. The means of remaining classes
do not need updating as these classes were not updated in the increment. We also update the total
mean (**m**).

**m**^{0}_{Ej}^{(x)}= *n*_{Ej}**m***Ej*(*x*)+ ¯**x***j*

*n**Ej* + 1 (4.1)

**m**^{0}_{E} = *n**E***m***E* +*v***m**¯*E*

*n**E* +*v* = *n*_{E}**m***E*+^{P}^{v}_{j=1}**y**¯_{j}

*n**E*+*v* (4.2)

**m**^{0} = *n***m**+*v***m**¯

*n*+*v* = *n***m**+^{P}^{v}_{j=1}¯**y**_{j}

*n*+*v* (4.3)

**C) Updating the within-class scatter matrix-** As the within-class scatter of classes other
than*E* does not change, we only update the scatter of class*E*. The scatter of the rest of the classes
does not need recomputing.

**S**^{0}_{W} = ^{X}^{c}

*i*=1*,i*6=*E*

**S***W**i*+**S**^{0}_{W}_{E}

=**S***W* + *v n**E*

(*n**E* +*v*)( ¯**m***E*−**m***E*) ( ¯**m***E*−**m***E*)^{T} +^{X}^{v}

*j*=1

**y**¯_{j}−**m***E* **y**¯_{j} −**m***E*

*T* (4.4)

**Algorithm 1** MvIDDA algorithm
**Input :**

- A trained model *φ*that consists of:

- Data sample counts: *n*,*n**i*,*n**ij*

- Means: **m**,**m***i*,**m***ij*

- Scatter matrices: **S**,**D**

- Set of class labels of existing data samples: C - Set of new data samples: ¯X

- Number of new data samples: ¯*n*

- Set of class labels of new data samples: ¯C
**while** new data is encountered **do**

**if** *n*¯== 1 **then**
**if** C ∈ C¯ **then**

Update *n*,*n**i*,*n**ij*

Update **m**,**m***i*,**m***ij* using Eq.(4.29)-(4.31)
Update **S**using Eq.(4.33)

Update **D**using Eq.(4.35)
**else**Update*n*,*n*_{i},*n*_{ij}

Update**m**, **m***i*,**m***ij* using Eq.(4.8)-(4.10)
Update**S**using Eq.(4.12)

Update**D**using Eq.(4.14)
C=C ∪C¯

**end if**
**else****if** C ∈ C¯ **then**

Update*n*,*n**i*,*n**ij*

Update**m**,**m***i*, **m***ij* using Eq.(4.15)-(4.17)
Update**S**using Eq.(4.19)

Update**D**using Eq.(4.21)
**else**Update*n*,*n*_{i},*n*_{ij}

Update**m**,**m***i*, **m***ij* using Eq.(4.36)-(4.38)
Update**S**using Eq.(4.40)

Update**D**using Eq.(4.42)
C=C ∪C¯

**end if**
**end if**

Compute the projection matrix**W**^{opt} using Eq.(2.5)
**end while**

**Output :**

- Updated model*φ*

- The projection matrix**W**^{opt}

and the reformulation of above equation is,

**S**^{0}_{jr} =

**S***jr*+_{v(n}^{n}^{E}

*E*+*v*)

¯**x***j*−**m***Ej*(*x*) **x**¯*j*−**m***Ej*(*x*)*T*

+ ¯**x***j*¯**x**^{T}_{j} −^{1}_{v}¯**x***j***x**¯^{T}_{j} *j*=*r*
**S***jr*+_{v(n}^{n}^{E}

*E*+*v*)

¯**x***j*−**m***Ej*(*x*) **x**¯*r*−**m***Er*(*x*)*T*

−^{1}_{v}**x**¯*j***x**¯^{T}_{r} *j*6=*r*

(4.5)

For detailed derivation of **S**^{0}_{W} and **S**^{0}_{jr} refer to Appendix-B.

**D) Updating the between-class scatter matrix-** The between-class scatter depends on the
total mean and class means. Hence, it has to be recalculated as the total mean and the class mean
of class*E* are updated after the increment.

**S**^{0}_{B}= ^{X}^{c}

*i*=1*,i*6=*E*

*n*_{i}(**m***i*−**m**^{0})(**m***i*−**m**^{0})^{T} +*n*^{0}_{E}(**m**^{0}_{E}−**m**^{0})(**m**^{0}_{E}−**m**^{0})^{T}

= ^{X}^{c}

*i*=1

*n*^{0}_{i}(**m**^{0}_{i}−**m**^{0})(**m**^{0}_{i}−**m**^{0})^{T}

(4.6)

and the reformulated between-class scatter is,

**D**^{0}_{jr}= ^{X}^{c}

*i*=1

*n*^{0}_{ij} *n*^{0}_{ir}

*n*^{0}_{i} **m**^{0}_{ij}^{(x)}**m**^{0}_{ir}^{(x)}^{T} − 1
*n*^{0}

*c*

X

*i*=1

*n*^{0}_{ij} **m**^{0}_{ij}^{(x)}

! _{c}
X

*i*=1

*n*^{0}_{ir}**m**^{0}_{ir}^{(x)}

!*T*

(4.7)

For detailed derivation of **S**^{0}_{B} and**D**^{0}_{jr} refer to Appendix-A.

**4.1.1.2 Sequential Increment and New Class**

The second case is when the newly added data sample belongs to a new class *N*. Let us denote
this data sample by ¯X ={**x**¯*j*|*j* = 1*,*· · · *, v*}and ¯**x***j* ∈R^{p}^{j}. Let ¯Y ={**y**¯_{j} =**W**^{T}_{j}**x**¯*j*|*j* = 1*,*· · ·*, v*} be
the projection of ¯X onto the common discriminant space.

**A) Updating the number of data samples-** As this is the first data sample in its class, we
initialize the number of data samples per class per view for this new class as, *n*_{N j} = 1. Also, the
number of data samples per class, *n*_{N} =*v* and updated total number of data samples, *n*^{0} =*n*+*v*.

Both,*n**ij* and *n**i* for*i*∈ C do not change.

**B) Updating the means-**

**m**^{0}_{N j}^{(x)}= ¯**m**^{(x)}_{N j} = ¯**x***j* (4.8)

**m**^{0}_{N} = ¯**m***N* = 1
*v*

*v*

X

*j*=1

**y**^{0}_{j} (4.9)

**m**^{0} = *n***m**+*v***m**¯

*n*+*v* = *n***m**+^{P}^{v}_{j=1}**y**¯_{j}

*n*+*v* (4.10)

**C) Updating the within-class scatter matrix-** We only add the within-class scatter of the
new class to the old**S***W*, as the within-class scatter of existing classes does not change.

**S**^{0}_{W} =**S***W* +^{X}^{v}

*j*=1

(¯**y**_{j}−**m**¯*N*)(¯**y**_{j}−**m**¯*N*)^{T} (4.11)
and the reformulation of above equation is,

**S**^{0}_{jr}=

**S***jr*+ ¯**x***j* ¯**x**^{T}_{j} −_{v}^{1}2**x**¯*j* **x**¯^{T}_{j} *j*=*r*
**S***jr*−_{v}^{1}2**x**¯*j* **x**¯^{T}_{r} *j*6=*r*

(4.12)

For detailed derivation of **S**^{0}_{W} and **S**^{0}_{jr} refer to Appendix-C.

**D) Updating the between-class scatter matrix-** Like before, the between-class scatter has
to be recalculated as,

**S**^{0}_{B}= ^{X}^{c}

*i*=1

*n*_{i}(**m***i*−**m**^{0})(**m***i*−**m**^{0})^{T} +*v*( ¯**m***N* −**m**^{0})( ¯**m***N* −**m**^{0})^{T}

= ^{c+1}^{X}

*i*=1

*n*^{0}_{i}(**m**^{0}_{i}−**m**^{0})(**m**^{0}_{i}−**m**^{0})^{T}

(4.13)

and the reformulated between-class scatter is,

**D**^{0}_{jr} = ^{c+1}^{X}

*i*=1

*n*^{0}_{ij} *n*^{0}_{ir}

*n*^{0}_{i} **m**^{0}_{ij}^{(x)}**m**^{0}_{ir}^{(x)}^{T} − 1
*n*^{0}

*c*+1

X

*i*=1

*n*^{0}_{ij} **m**^{0}_{ij}^{(x)}

! _{c+1}
X

*i*=1

*n*^{0}_{ir} **m**^{0}_{ir}^{(x)}

!*T*

(4.14)

After the completion of all four steps, we add the new class in the set of existing classes (C).

**4.1.1.3 Chunk Increment and Existing Class**

For the first case of chunk increment, ¯*n*_{i} of the ¯*n*new data samples belong to class*i*∈ C, meaning,
none of the new data samples belong to a class that has not yet been introduced. We denote a
chunk of new data samples by, ¯X ={**x**¯*ijk*|*i*= 1*,*· · · *, c*;*j* = 1*,*· · · *, v*;*k*= 1*,*· · · *,n*¯_{ij}}and ¯**x***ijk*∈R^{p}^{j}.
Let ¯Y ={¯**y***ijk* =**W**^{T}_{j}**x**¯*ijk*|*i*= 1*,*· · ·*, c*;*j*= 1*,*· · ·*, v*;*k*= 1*,*· · ·*,*¯*n*_{ij}} be the projection of ¯X onto the
common discriminant space.

**A) Updating the number of data samples-**

*n*^{0}_{ij} =*n*_{ij}+ ¯*n*_{ij}*, n*^{0}_{i}=*n*_{i}+ ¯*n*_{i} and *n*^{0} =*n*+ ¯*n*
for*i*= 1*,*· · · *, c*and *j*= 1*,*· · · *, v*.

**B) Updating the means-**

**m**^{0}_{ij}^{(x)} = *n**ij***m***ij*(*x*)+ ¯*n**ij***m**¯*ij*(*x*)

*n**ij*+ ¯*n**ij* = *n*_{ij}**m***ij*(*x*)+^{P}^{n}_{k=1}^{¯}^{ij} **x**¯*ijk*

*n**ij* + ¯*n**ij* (4.15)

**m**^{0}_{i}= *n**i***m***i*+ ¯*n**i***m**¯*i*

*n**i*+ ¯*n**i* = *n*_{i}**m***i*+^{P}^{v}_{j=1}^{P}^{¯}^{n}_{k=1}^{ij} **y**¯_{ijk}

*n**i*+ ¯*n**i* (4.16)

**m**^{0} = *n***m**+ ¯*n***m**¯

*n*+ ¯*n* = *n***m**+^{P}^{c}_{i=1}^{P}^{v}_{j=1}^{P}^{n}_{k=1}^{¯}^{ij} **y**¯_{ijk}

*n*+ ¯*n* (4.17)

**C) Updating the within-class scatter matrix-** The within-class scatter of only the classes
to which new data samples were added is updated. Hence, we have,

**S**^{0}_{W} =**S***W* +^{X}^{c}

*i*=1

" _{v}
X

*j*=1

¯
*n**ij*

X

*k*=1

**y**¯_{ijk}**y**¯^{T}_{ijk}−**y**¯_{ijk}**m***i**T*

+ *n*¯*i**n**i*

(*n**i*+ ¯*n*_{i})( ¯**m***i*−**m***i*) ( ¯**m***i*−**m***i*)^{T}

#

(4.18) and the reformulation of above equation is,

**S**^{0}_{jr}=

**S***jj*+ ^{P}^{c}

*i*=1

*v*¯*n**i*+*n**i*

¯

*n**i**n**i*(*n**i*+¯*n**i*)^{2}**aa**^{T} −^{n}^{¯}^{ij}_{n}_{¯}^{n}^{¯}^{ij}

*i* **m**^{(x)}_{ij} **m**^{(x)}_{ij} ^{T} + ^{n}^{¯}^{P}^{ij}

*k*=1

**x**¯*ijk***x**¯^{T}_{ijk}^{} *j*=*r*
**S***jr*+ ^{P}^{c}

*i*=1

*v*¯*n**i*+*n**i*

¯

*n**i**n**i*(*n**i*+¯*n**i*)^{2}**ab**^{T} −^{n}^{¯}^{ij}_{n}_{¯}^{n}^{¯}^{ir}

*i* **m**^{(x)}_{ij} **m**^{(x)}_{ir} ^{T}^{} *j*6=*r*

(4.19)

Where,

**a**= ¯*n*_{ij}*n*_{i}**m**¯^{(x)}_{ij} −*n*¯_{i}*n*_{ij}**m**^{(x)}_{ij} and**b**= ¯*n*_{ir}*n*_{i}**m**¯^{(x)}_{ir} −*n*¯_{i}*n*_{ir}**m**^{(x)}_{ir}
For detailed derivation of **S**^{0}_{W} and **S**^{0}_{jr} refer to Appendix-D.

**D) Updating the between-class scatter matrix-** The between-class scatter is recalculated
as,

**S**^{0}_{B}=^{X}^{c}

*i*=1

*n*^{0}_{i}(**m**^{0}_{i}−**m**^{0})(**m**^{0}_{i}−**m**^{0})^{T} (4.20)
and the reformulated between-class scatter is,

**D**^{0}_{jr}= ^{X}^{c}

*i*=1

*n*^{0}_{ij} *n*^{0}_{ir}

*n*^{0}_{i} **m**^{0}_{ij}^{(x)}**m**^{0}_{ir}^{(x)}^{T} − 1
*n*^{0}

*c*

X

*i*=1

*n*^{0}_{ij} **m**^{0}_{ij}^{(x)}

! _{c}
X

*i*=1

*n*^{0}_{ir}**m**^{0}_{ir}^{(x)}

!*T*

(4.21)

**4.1.1.4 Chunk Increment and New Class**

In second case of chunk increment, we assume that out of ¯*n*new data samples, some samples belong
to new classes. The number of new classes may be one or more. Here, we denote a chunk of new
data samples by, ¯X = {**x**¯*ijk*|*i* = 1*,*· · ·*, c*^{0};*j* = 1*,*· · · *, v*;*k* = 1*,*· · · *,n*¯_{ij}} and ¯**x***ijk* ∈ R^{p}^{j}. Here, *c*^{0}
is the number of classes after adding the new classes. Let ¯Y ={**y**¯*ijk* =**W**^{T}*j***x**¯*ijk*|*i*= 1*,*· · ·*, c*^{0};*j* =
1*,*· · · *, v*;*k*= 1*,*· · · *,n*¯*ij*} be the projection of ¯X onto the common discriminant space.

**A) Updating the number of data samples-**

*n*^{0}_{ij} =*n**ij*+ ¯*n**ij**, n*^{0}_{i}=*n**i*+ ¯*n**i* and *n*^{0} =*n*+ ¯*n*
for*i*= 1*,*· · · *, c*^{0} and*j* = 1*,*· · · *, v*.

**B) Updating the means-**

**m**^{0}_{ij}^{(x)} = *n**ij***m***ij*(*x*)+ ¯*n**ij***m**¯*ij*(*x*)

*n**ij*+ ¯*n**ij* = *n*_{ij}**m***ij*(*x*)+^{P}^{n}_{k=1}^{¯}^{ij} **x**¯*ijk*

*n**ij* + ¯*n**ij* (4.22)

**m**^{0}*i*= *n*_{i}**m***i*+ ¯*n*_{i}**m**¯*i*

*n**i*+ ¯*n**i* = *n**i***m***i*+^{P}^{v}_{j=1}^{P}^{¯}^{n}_{k=1}^{ij} **y**¯_{ijk}

*n**i*+ ¯*n**i* (4.23)

**m**^{0} = *n***m**+ ¯*n***m**¯

*n*+ ¯*n* = *n***m**+^{P}^{c}_{i=1}^{P}^{v}_{j=1}^{P}^{n}_{k=1}^{¯}^{ij} **y**¯_{ijk}

*n*+ ¯*n* (4.24)

**C) Updating the within-class scatter matrix-** The within-class scatter of the existing and
the new classes to which new data samples were added is updated. Hence, we have,

**S**^{0}_{W} =**S***W* + ^{c}

0

X

*i*=1

" _{v}
X

*j*=1

¯
*n**ij*

X

*k*=1

**y**¯_{ijk}**y**¯^{T}_{ijk}−**y**¯_{ijk}**m**¯*i**T*

+ *n*¯*i**n**i*

(*n**i*+ ¯*n**i*)( ¯**m***i*−**m***i*) ( ¯**m***i*−**m***i*)^{T}

#

(4.25) and the reformulation of above equation is,

**S**^{0}_{jr}=

**S***jj*+ ^{c}

0

P

*i*=1

*v*¯*n**i*+*n**i*

¯

*n**i**n**i*(*n**i*+¯*n**i*)^{2}**aa**^{T} −^{n}^{¯}^{ij}_{n}_{¯}^{n}^{¯}^{ij}

*i* **m**¯^{(x)}_{ij} **m**¯^{(x)}_{ij} ^{T} + ^{n}^{¯}^{P}^{ij}

*k*=1

**x**¯*ijk***x**¯^{T}_{ijk}^{} *j*=*r*
**S***jr*+ ^{P}^{c}^{0}

*i*=1

*v*¯*n**i*+*n**i*

¯

*n**i**n**i*(*n**i*+¯*n**i*)^{2}**ab**^{T} −^{n}^{¯}^{ij}_{n}_{¯}^{n}^{¯}^{ir}

*i* **m**¯^{(x)}_{ij} **m**¯^{(x)}_{ir} ^{T}^{} *j*6=*r*

(4.26)

Where,

**a**= ¯*n**ij**n**i***m**¯^{(x)}_{ij} −*n*¯*i**n**ij***m**^{(x)}_{ij} and**b**= ¯*n**ir**n**i***m**¯^{(x)}_{ir} −*n*¯*i**n**ir***m**^{(x)}_{ir}

The derivation of **S**^{0}_{W} and **S**^{0}_{jr} in this case is the same as in Appendix-D, if we set *c*=*c*^{0}. Hence,
no separate derivation is included.

**D) Updating the between-class scatter matrix-** The between-class scatter is recalculated
as,

**S**^{0}_{B}= ^{c}

0

X

*i*=1

*n*^{0}_{i}(**m**^{0}_{i}−**m**^{0})(**m**^{0}_{i}−**m**^{0})^{T} (4.27)
and the reformulated between-class scatter is,

**D**^{0}_{jr}= ^{c}

0

X

*i*=1

*n*^{0}_{ij} *n*^{0}_{ir}

*n*^{0}_{i} **m**^{0}_{ij}^{(x)}**m**^{0}_{ir}^{(x)}^{T} − 1
*n*^{0}

*c*^{0}

X

*i*=1

*n*^{0}_{ij} **m**^{0}_{ij}^{(x)}

*c*^{0}

X

*i*=1

*n*^{0}_{ir} **m**^{0}_{ir}^{(x)}

*T*

(4.28)

After the completion of all four steps, we add the new classes in the set of existing classes (C).

It is possible to obtain the formulations of*chunk increment and existing class* if we set*c*^{0} =*c*
in the formulations in Section 4.1.1.4. We can also obtain the sequential increment formulations
for both cases by setting*l*= 1 in the two chunk increment formulations. As these formulations are
inherently similar to the batch MvDA, we can derive the batch MvDA formulations from MvIDDA
formulations. This is based on the base requirement of incremental methods that the discriminant
spaces obtained by the incremental method must be identical to that of the batch method.