# Incremental Tensor Principal Component Analysis for Handwritten Digit Recognition

Authors: Chang Liu; Tao Yan; WeiDong Zhao; YongHong Liu; Dan Li; Feng Lin; JiLiu Zhou
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

To overcome the shortcomings of traditional dimensionality reduction algorithms, incremental tensor principal component analysis (ITPCA) based on updated-SVD technique algorithm is proposed in this paper. This paper proves the relationship between PCA, 2DPCA, MPCA, and the graph embedding framework theoretically and derives the incremental learning procedure to add single sample and multiple samples in detail. The experiments on handwritten digit recognition have demonstrated that ITPCA has achieved better recognition performance than that of vector-based principal component analysis (PCA), incremental principal component analysis (IPCA), and multilinear principal component analysis (MPCA) algorithms. At the same time, ITPCA also has lower time and space complexity.


---

## Body

## 1. Introduction

Pattern recognition and computer vision require processing a large amount of multi-dimensional data, such as image and video data. Until now, a large number of dimensionality reduction algorithms have been investigated. These algorithms project the whole data into a low-dimensional space and construct new features by analyzing the statistical relationship hidden in the data set. The new features often give good information or hints about the data’s intrinsic structure. As a classical dimensionality reduction algorithm, principal component analysis has been applied in various applications widely.Traditional dimensionality reduction algorithms generally transform each multi-dimensional data into a vector by concatenating rows, which is called Vectorization. Such kind of the vectorization operation has largely increased the computational cost of data analysis and seriously destroys the intrinsic tensor structure of high-order data. Consequently, tensor dimensionality reduction algorithms are developed based on tensor algebra [1–10]. Reference [10] has summarized existing multilinear subspace learning algorithms for tensor data. Reference [11] has generalized principal component analysis into tensor space and presented multilinear principal component analysis (MPCA). Reference [12] has proposed the graph embedding framework to unify all dimensionality reduction algorithms.Furthermore, traditional dimensionality reduction algorithms generally employ off-line learning to deal with new added samples, which aggravates the computational cost. To address this problem, on-line learning algorithms are proposed [13, 14]. In particular, reference [15] has developed incremental principal component analysis (IPCA) based on updated-SVD technique. But most on-line learning algorithms focus on vector-based methods, only a limited number of works study incremental learning in tensor space [16–18].To improve the incremental learning in tensor space, this paper presents incremental tensor principal component analysis (ITPCA) based on updated-SVD technique combining tensor representation with incremental learning. This paper proves the relationship between PCA, 2DPCA, MPCA, and the graph embedding framework theoretically and derives the incremental learning procedure to add single sample and multiple samples in detail. The experiments on handwritten digit recognition have demonstrated that ITPCA has achieved better performance than vector-based incremental principal component analysis (IPCA) and multilinear principal component analysis (MPCA) algorithms. At the same time, ITPCA also has lower time and space complexity than MPCA.


## 2. Tensor Principal Component Analysis

In this section, we will employ tensor representation to express high-dimensional image data. Consequently, a high-dimensional image dataset can be expressed as a tensor datasetX
=
{
X
1
,
…
,
X
M
}, where X
i
∈
ℝ
I
1
×
⋯
×
I
N is an N dimensional tensor and M is the number of samples in the dataset. Based on the representation, the following definitions are introduced.Definition 1.
For tensor datasetX, the mean tensor is defined as follows:
(1)
X
¯
=
1
M
∑
i
=
1
M
X
i
∈
ℝ
I
1
×
⋯
×
I
N
.Definition 2.
The unfolding matrix of the mean tensor along thenth dimension is called the mode-n mean matrix and is defined as follows:
(2)
X
¯
(
n
)
=
1
M
∑
i
=
1
M
X
i
(
n
)
∈
ℝ
I
n
×
∏
i
=
1
i
≠
n
N
I
i
.Definition 3.
For tensor datasetX, the total scatter tensor is defined as follows:
(3)
Ψ
X
=
∑
m
=
1
M
∥
X
m
-
X
¯
∥
2
,
where ∥
A
∥ is the norm of the tensor.Definition 4.
For tensor datasetX, the mode-n total scatter matrix is defined as follows:
(4)
C
(
n
)
=
∑
i
=
1
M
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
,
where X
¯
(
n
) is the mode-n mean matrix and X
i
(
n
) is the mode-n unfolding matrix of tensor X
i.Tensor PCA is introduced in [11, 19]. The target is to compute N orthogonal projective matrices {
U
(
n
)
∈
ℝ
I
n
×
P
n
,
n
=
1
,
…
,
N
} to maximize the total scatter tensor of the projected low-dimensional feature as follows:
(5)
f
{
U
(
n
)
,
n
=
1
,
…
,
N
}
=
arg
⁡
max
⁡
U
(
n
)
⁡
Ψ
y
=
arg
⁡
max
⁡
U
(
n
)
⁡
∑
m
=
1
M
∥
Y
m
-
Y
¯
∥
2
,
where Y
m
=
X
m
×
U
(
1
)
T
1
×
U
(
2
)
T
2
×
⋯
U
(
n
-
1
)
T
n
-
1
×
U
(
n
+
1
)
T
n
+
1
×
⋯
×
U
(
N
)
T
N.Since it is difficult to solveN orthogonal projective matrices simultaneously, an iterative procedure is employed to approximately compute these N orthogonal projective matrices. Generally, since it is assumed that the projective matrices {
U
(
1
)
,
…
,
U
(
n
-
1
)
,
U
(
n
+
1
)
,
…
U
(
N
)
} are known, we can solve the following optimized problem to obtain U
(
n
):
(6)
arg
⁡
max
⁡
⁡
∑
m
=
1
M
(
C
m
(
n
)
C
m
(
n
)
T
)
,
where C
m
=
(
X
m
-
X
¯
)
×
U
(
1
)
T
1
×
U
(
2
)
T
2
×
⋯
U
(
n
-
1
)
T
n
-
1
×
U
(
n
+
1
)
T
n
+
1
×
⋯
×
U
(
N
)
T
N and C
m
(
n
) is the mode-n unfolding matrix of tensor C
m.According to the above analysis, it is easy to derive the following theorems.Theorem 5 (see [11]).
For the order of tensor datan
=
1, that is, for the first-order tensor, the objective function of MPCA is equal to that of PCA.Proof.
For the first-order tensor,X
m
∈
ℝ
I
×
1 is a vector, then (6) is
(7)
∑
m
=
1
M
(
C
m
(
n
)
C
m
(
n
)
T
)
=
∑
m
=
1
M
(
U
T
(
X
m
-
X
¯
)
(
X
m
-
X
¯
)
T
U
)
.
So MPCA for first-order tensor is equal to vector-based PCA.Theorem 6 (see [11]).
For the order of tensor datan
=
2, that is, for the second-order tensor, the objective function of MPCA is equal to that of 2DsPCA.Proof.
For the second-order tensor,X
m
∈
ℝ
I
1
×
I
2 is a matrix; it is needed to solve two projective matrices U
(
1
) and U
(
2
), then (5) becomes
(8)
∑
m
=
1
M
∥
Y
m
-
Y
¯
∥
2
=
∑
m
=
1
M
∥
U
(
1
)
T
(
X
m
-
X
-
)
U
(
2
)
∥
2
.
The above equation exactly is the objective function of B2DPCA (bidirectional 2DPCA) [20–22]. Letting U
(
2
)
=
I, the projective matrix U
(
1
) is solved. In this case, the objective function is
(9)
∑
m
=
1
M
∥
Y
m
-
Y
¯
∥
2
=
∑
m
=
1
M
∥
U
(
1
)
T
(
X
m
-
X
-
)
I
∥
2
.
Then the above equation is simplified into the objective function of row 2DPCA [23, 24]. Similarly, letting U
(
1
)
=
I, the projective matrix U
(
2
) is solved; the objective function is
(10)
∑
m
=
1
M
∥
Y
m
-
Y
¯
∥
2
=
∑
m
=
1
M
∥
I
T
(
X
m
-
X
-
)
U
(
2
)
∥
2
.
Then the above equation is simplified into the objective function of column 2DPCA [23, 24].Although vector-based and 2DPCA can be respected as the special cases of MPCA, MPCA and 2DPCA employ different techniques to solve the projective matrices. 2DPCA carries out PCA to row data and column data, respectively, and MPCA employs an iterative solution to computeN projective matrices. If it is supposed that the projective matrices {
U
(
1
)
,
…
,
U
(
n
-
1
)
,
U
(
n
+
1
)
,
…
U
(
N
)
} are known, then U
(
n
) is solved. Equation (6) can be expressed as follows:
(11)
C
(
n
)
=
∑
i
=
1
M
(
(
X
i
(
n
)
-
X
¯
(
n
)
)
×
U
(
k
)
T
k
|
k
=
1
k
≠
n
N
)
f
f
f
f
f
f
×
(
(
X
i
(
n
)
-
X
¯
(
n
)
)
×
U
(
k
)
T
k
|
k
=
1
k
≠
n
N
)
T
=
∑
i
=
1
M
(
(
X
i
(
n
)
-
X
¯
(
n
)
)
U
(
-
n
)
)
(
(
X
i
(
n
)
-
X
¯
(
n
)
)
U
(
-
n
)
)
T
=
∑
i
=
1
M
(
(
X
i
(
n
)
-
X
¯
(
n
)
)
U
(
-
n
)
U
(
-
n
)
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
)
,
where U
(
-
n
)
=
U
(
N
)
⋯
⊗
U
(
n
+
1
)
⊗
U
(
n
-
1
)
⋯
⊗
U
(
1
).Because(12)
U
(
-
n
)
U
(
-
n
)
T
=
(
U
(
N
)
⋯
⊗
U
(
n
+
1
)
⊗
U
(
n
-
1
)
⋯
⊗
U
(
1
)
)
×
(
U
(
N
)
⋯
⊗
U
(
n
+
1
)
⊗
U
(
n
-
1
)
⋯
⊗
U
(
1
)
)
T
.
Based on the Kronecker product, we can get the following:
(13)
(
A
⊗
B
)
T
=
A
T
⊗
B
T
,
(
A
⊗
B
)
(
C
⊗
D
)
=
A
C
⊗
B
D
.
So
(14)
U
(
-
n
)
U
(
-
n
)
T
=
U
(
N
)
U
(
N
)
T
⋯
⊗
U
(
n
+
1
)
U
(
n
+
1
)
T
⊗
U
(
n
-
1
)
U
(
n
-
1
)
T
⋯
⊗
U
(
1
)
U
(
1
)
T
.
Since U
(
i
)
∈
ℝ
I
i
×
I
i is an orthogonal matrix, U
(
i
)
U
(
i
)
T
=
I, i
=
1
,
…
,
N, i
≠
n, and U
(
-
n
)
U
(
-
n
)
T
=
I.If the dimensions of projective matrices do not change in iterative procedure, then(15)
C
(
n
)
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
.
The above equation is equal to B2DPCA. Because MPCA updates projective matrices during iterative procedure, it has achieved better performance than 2DPCA.Theorem 7.
MPCA can be unified into the graph embedding framework [12].Proof.
Based on the basic knowledge of tensor algebra, we can get the following:(16)
∑
m
=
1
M
∥
Y
m
-
Y
¯
∥
2
=
∑
m
=
1
M
∥
vec
⁡
(
Y
m
)
-
vec
⁡
(
Y
¯
)
∥
2
.
Letting y
m
=
vec
⁡
(
Y
m
), μ
=
vec
⁡
(
Y
¯
), we can get the following:
(17)
∑
i
=
1
K
∥
y
i
-
μ
∥
2
=
∑
i
=
1
K
(
y
i
-
μ
)
(
y
i
-
μ
)
T
=
∑
i
=
1
K
(
y
i
-
1
N
∑
j
=
1
N
y
j
)
(
y
i
-
1
N
∑
j
=
1
N
y
j
)
T
=
∑
i
=
1
K
(
y
i
y
i
T
-
1
N
y
i
(
∑
j
=
1
K
y
j
)
T
-
1
N
(
∑
j
=
1
K
y
j
)
y
i
T
f
f
f
f
f
f
f
+
1
N
2
(
∑
j
=
1
K
y
j
)
(
∑
j
=
1
K
y
j
)
T
)
=
∑
i
=
1
K
y
i
y
i
T
-
1
N
∑
i
=
1
K
y
i
(
∑
j
=
1
K
y
j
)
T
-
1
N
∑
i
=
1
K
∑
j
=
1
K
y
j
y
i
T
+
1
N
(
∑
j
=
1
K
y
j
)
(
∑
j
=
1
K
y
j
)
T
=
∑
i
=
1
K
y
i
y
i
T
-
1
N
∑
i
=
1
K
∑
j
=
1
K
y
i
y
j
T
=
∑
i
=
1
K
(
∑
j
=
1
K
W
i
j
)
y
i
y
i
T
-
∑
i
,
j
=
1
K
W
i
j
y
i
y
j
T
=
1
2
∑
i
,
j
=
1
K
W
i
j
(
y
i
y
i
T
+
y
j
y
j
T
-
y
i
y
j
T
-
y
j
y
i
T
)
=
1
2
∑
i
,
j
=
1
K
W
i
j
(
y
i
-
y
j
)
(
y
i
-
y
j
)
T
=
1
2
∑
i
,
j
=
1
K
W
i
j
∥
y
i
-
y
j
∥
F
2
,
where the similarity matrix W
∈
ℝ
M
×
M; for any i
,
j, we have W
i
j
=
1
/
K. So (16) can be written as follows:
(18)
∑
m
=
1
M
∥
Y
m
-
Y
¯
∥
2
=
1
2
∑
i
,
j
=
1
M
W
i
j
∥
Y
i
-
Y
j
∥
2
=
1
2
∑
i
,
j
=
1
M
W
i
j
∥
X
i
×
U
(
n
)
n
|
n
=
1
N
-
X
j
×
U
(
n
)
n
|
n
=
1
N
∥
2
.
So the theorem is proved.


## 3. Incremental Tensor Principal Component Analysis

### 3.1. Incremental Learning Based on Single Sample

Given initial training samplesX
old
=
{
X
1
,
…
,
X
K
}, X
i
∈
ℝ
I
1
×
⋯
×
I
N, when a new sample X
new
∈
ℝ
I
1
×
⋯
×
I
N is added, the training dataset becomes X
=
{
X
old
,
X
new
}.The mean tensor of initial samples is(19)
X
¯
old
=
1
K
∑
i
=
1
K
X
i
.
The covariance tensor of initial samples is
(20)
C
old
=
∑
i
=
1
K
∥
X
i
-
X
¯
old
∥
2
.
The mode-n covariance matrix of initial samples is
(21)
C
old
(
n
)
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
)
(
X
i
(
n
)
-
X
¯
old
)
T
.
When the new sample is added, the mean tensor is
(22)
X
¯
=
1
K
+
1
∑
i
=
1
K
+
1
X
i
=
1
K
+
1
(
∑
i
=
1
K
X
i
+
X
new
)
=
1
K
+
1
(
K
X
¯
old
+
X
new
)
.
The mode-n covariance matrix is expressed as follows:
(23)
C
(
n
)
=
∑
i
=
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
+
(
X
new
(
n
)
-
X
¯
(
n
)
)
(
X
new
(
n
)
-
X
¯
(
n
)
)
T
,
where the first item of (23) is
(24)
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
+
X
¯
old
(
n
)
-
X
¯
(
n
)
)
×
(
X
i
(
n
)
-
X
¯
old
(
n
)
+
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
[
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
]
×
[
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
]
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
+
K
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
+
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
+
K
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
=
C
old
(
n
)
+
K
(
X
¯
old
(
n
)
-
K
X
¯
old
(
n
)
+
X
new
(
n
)
K
+
1
)
×
(
X
¯
old
(
n
)
-
K
X
¯
old
(
n
)
+
X
new
(
n
)
K
+
1
)
T
=
C
old
(
n
)
+
K
(
K
+
1
)
2
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
T
.
The second item of (23) is
(25)
(
X
new
(
n
)
-
X
¯
(
n
)
)
(
X
new
(
n
)
-
X
¯
(
n
)
)
T
=
(
X
new
(
n
)
-
X
¯
(
n
)
)
(
X
new
(
n
)
-
X
¯
(
n
)
)
T
=
(
X
new
(
n
)
-
K
X
¯
old
(
n
)
+
X
new
(
n
)
K
+
1
)
(
X
new
(
n
)
-
K
X
¯
old
(
n
)
+
X
new
(
n
)
K
+
1
)
T
=
K
2
(
K
+
1
)
2
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
T
.Consequently, the mode-n covariance matrix is updated as follows:
(26)
C
(
n
)
=
C
old
(
n
)
+
K
K
+
1
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
T
.
Therefore, when a new sample is added, the projective matrices are solved according to the eigen decomposition on (26).


### 3.2. Incremental Learning Based on Multiple Samples

Given an initial training datasetX
old
=
{
X
1
,
…
,
X
K
}, X
i
∈
ℝ
I
1
×
⋯
×
I
N, when new samples are added into training dataset, X
new
=
{
X
K
+
1
,
…
,
X
K
+
T
}, then training dataset becomes into X
=
{
X
1
,
…
,
X
K
,
X
K
+
1
,
…
,
X
K
+
T
}. In this case, the mean tensor is updated into the following:
(27)
X
¯
=
1
K
+
T
∑
i
=
1
K
+
T
X
i
=
1
K
+
T
(
∑
i
=
1
K
X
i
+
∑
i
=
K
+
1
K
+
T
X
i
)
=
1
K
+
T
(
K
X
¯
old
+
T
X
¯
new
)
.
Its mode-n covariance matrix is
(28)
C
(
n
)
=
∑
i
=
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
+
∑
i
=
K
+
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
.
The first item in (28) is written as follows:
(29)
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
+
K
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
+
∑
i
=
1
K
[
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
f
f
f
f
f
f
f
f
f
f
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
]
,
where
(30)
∑
i
=
1
K
[
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
f
f
f
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
]
=
K
X
¯
old
(
n
)
X
¯
old
(
n
)
T
-
K
X
¯
old
(
n
)
X
¯
(
n
)
T
-
K
X
¯
old
(
n
)
X
¯
old
(
n
)
T
+
K
X
¯
old
(
n
)
X
¯
(
n
)
T
+
K
X
¯
old
(
n
)
X
¯
old
(
n
)
T
-
K
X
¯
old
(
n
)
X
¯
old
(
n
)
T
-
K
X
¯
(
n
)
X
¯
old
(
n
)
T
+
K
X
¯
(
n
)
X
¯
old
(
n
)
T
=
0
,
K
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
=
K
T
2
(
K
+
T
)
2
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
.
Putting (30) into (29), then (29) becomes as follows:
(31)
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
C
old
(
n
)
+
K
T
2
(
K
+
T
)
2
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
.
The second item in (28) is written as follows:
(32)
∑
i
=
K
+
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
C
new
(
n
)
+
T
(
X
¯
new
(
n
)
-
X
¯
(
n
)
)
(
X
¯
new
(
n
)
-
X
¯
(
n
)
)
T
,
where
(33)
T
(
X
¯
new
(
n
)
-
X
¯
(
n
)
)
(
X
¯
new
(
n
)
-
X
¯
(
n
)
)
T
=
K
2
T
(
K
+
T
)
2
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
Then (32) becomes as follows:
(34)
∑
i
=
K
+
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
C
new
(
n
)
+
K
2
T
(
K
+
T
)
2
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
Putting (31) and (34) into (28), then we can get the following:
(35)
C
(
n
)
=
C
old
(
n
)
+
C
new
(
n
)
+
K
T
K
+
T
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
.
It is worthy to note that when new samples are available, it has no need to recompute the mode-n covariance matrix of all training samples. We just have to solve the mode-n covariance matrix of new added samples and the difference between original training samples and new added samples. However, like traditional incremental PCA, eigen decomposition on C
(
n
) has been repeated once new samples are added. It is certain that the repeated eigen decomposition on C
(
n
) will cause heavy computational cost, which is called “the eigen decomposition updating problem.” For traditional vector-based incremental learning algorithm, the updated-SVD technique is proposed in [25] to fit the eigen decomposition. This paper will introduce the updated-SVD technique into tensor-based incremental learning algorithm.For original samples, the mode-n covariance matrix is
(36)
C
old
(
n
)
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
=
S
old
(
n
)
S
old
(
n
)
T
,
where S
old
(
n
)
=
[
X
1
(
n
)
-
X
¯
old
(
n
)
,
…
,
X
K
(
n
)
-
X
¯
old
(
n
)
]. According to the eigen decomposition S
old
(
n
)
=
svd
(
U
Σ
V
T
), we can get the following:
(37)
S
old
(
n
)
S
old
(
n
)
T
=
(
U
Σ
V
T
)
(
U
Σ
V
T
)
T
=
U
Σ
V
T
V
Σ
U
T
=
U
Σ
2
U
T
=
eig
(
C
old
(
n
)
)
.
So it is easy to derive that the eigen-vector of C
old
(
n
) is the left singular vector of S
old
(
n
) and the eigen-values correspond to the extraction of left singular values of S
old
(
n
).For new samples, the mode-n covariance matrix is
(38)
C
new
(
n
)
=
∑
i
=
K
+
1
K
+
T
(
X
i
(
n
)
-
X
¯
new
(
n
)
)
(
X
i
(
n
)
-
X
¯
new
(
n
)
)
T
=
S
new
(
n
)
S
new
(
n
)
T
,
where S
new
(
n
)
=
[
X
1
(
n
)
-
X
¯
new
(
n
)
,
…
,
X
K
(
n
)
-
X
¯
new
(
n
)
]. According to (35), the updated mode-n covariance matrix is defined as follows:
(39)
C
(
n
)
=
C
old
(
n
)
+
C
new
(
n
)
+
K
T
K
+
T
×
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
=
S
(
n
)
S
(
n
)
T
,
where S
(
n
)
=
[
S
old
(
n
)
,
S
new
(
n
)
,
K
T
/
(
K
+
T
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
]. Therefore, the updated projective matrix U
(
n
) is the eigen-vectors corresponding to the largest P
n eigen-values of S
(
n
). The main steps of incremental tensor principal component analysis are listed as follows:input: original samples and new added samples,
output:N projective matrices.Step 1.
Computing and saving(40)
eig
(
C
old
(
n
)
)
≈
[
U
r
(
n
)
,
Σ
r
(
n
)
]
.Step 2.
Fori
=
1
:
N
(41)
B
=
[
S
new
(
n
)
,
K
T
K
+
T
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
]
.
Processing QR decomposition for the following equation:(42)
QR
=
(
I
-
U
r
(
n
)
U
r
(
n
)
T
)
B
.
Processing SVD decomposition for the following equation:(43)
svd
[
Σ
r
(
n
)
U
r
(
n
)
T
B
0
R
]
=
U
^
Σ
^
V
^
T
.
Computing the following equation:(44)
[
S
old
(
n
)
,
B
]
≈
(
[
U
r
(
n
)
,
Q
]
U
^
)
Σ
^
(
[
V
r
(
n
)
0
0
I
]
V
^
)
T
.
Then the updated projective matrix is computed as follows:(45)
U
(
n
)
=
[
U
r
(
n
)
,
Q
]
U
^
,
end.Step 3.
Repeating the above steps until the incremental learning is finished.


### 3.3. The Complexity Analysis

For tensor datasetX
=
{
X
1
,
…
,
X
M
}, X
i
∈
ℝ
I
1
×
⋯
×
I
N, without loss of generality, it is assumed that all dimensions are equal, that is, I
1
=
⋯
=
I
N
=
I.Vector-based PCA converts all data into vector and constructs a data matrixX
∈
ℝ
M
×
D, D
=
I
N. For vector-based PCA, the main computational cost contains three parts: the computation of the covariance matrix, the eigen decomposition of the covariance matrix, and the computation of low-dimensional features. The time complexity to compute covariance matrix is O
(
M
I
2
N
), the time complexity of the eigen decomposition is O
(
I
3
N
), and the time complexity to compute low-dimensional features is O
(
M
I
2
N
+
I
3
N
).Letting the iterative number be 1, the time complexity to computing the mode-n covariance matrix for MPCA is O
(
M
N
I
N
+
1
), the time complexity of eigen decomposition is O
(
N
I
3
), and the time complexity to compute low-dimensional features is O
(
M
N
I
N
+
1
), so the total time complexity is O
(
M
N
I
N
+
1
+
N
I
3
). Considering the time complexity, MPCA is superior to PCA.For ITPCA, it is assumed thatT incremental datasets are added; MPCA has to recompute mode-n covariance matrix and conducts eigen decomposition for initial dataset and incremental dataset. The more the training samples are, the higher time complexity they have. If updated-SVD is used, we only need to compute QR decomposition and SVD decomposition. The time complexity of QR decomposition is O
(
N
I
N
+
1
). The time complexity of the rank-k decomposition of the matrix with the size of (
r
+
I
)
×
(
r
+
I
N
-
1
) is O
(
N
(
r
+
I
)
k
2
). It can be seen that the time complexity of updated-SVD has nothing to do with the number of new added samples.Taking the space complexity into account, if training samples are reduced into low-dimensional space and the dimension isD
=
∏
n
=
1
N
d
n, then PCA needs D
∏
n
=
1
N
I
n bytes to save projective matrices and MPCA needs ∑
n
=
1
N
I
n
d
n bytes. So MPCA has lower space complexity than PCA. For incremental learning, both PCA and MPCA need M
∏
n
=
1
N
I
n bytes to save initial training samples; ITPCA only need ∑
n
=
1
N
I
n
2 bytes to keep mode-n covariance matrix.


## 3.1. Incremental Learning Based on Single Sample

Given initial training samplesX
old
=
{
X
1
,
…
,
X
K
}, X
i
∈
ℝ
I
1
×
⋯
×
I
N, when a new sample X
new
∈
ℝ
I
1
×
⋯
×
I
N is added, the training dataset becomes X
=
{
X
old
,
X
new
}.The mean tensor of initial samples is(19)
X
¯
old
=
1
K
∑
i
=
1
K
X
i
.
The covariance tensor of initial samples is
(20)
C
old
=
∑
i
=
1
K
∥
X
i
-
X
¯
old
∥
2
.
The mode-n covariance matrix of initial samples is
(21)
C
old
(
n
)
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
)
(
X
i
(
n
)
-
X
¯
old
)
T
.
When the new sample is added, the mean tensor is
(22)
X
¯
=
1
K
+
1
∑
i
=
1
K
+
1
X
i
=
1
K
+
1
(
∑
i
=
1
K
X
i
+
X
new
)
=
1
K
+
1
(
K
X
¯
old
+
X
new
)
.
The mode-n covariance matrix is expressed as follows:
(23)
C
(
n
)
=
∑
i
=
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
+
(
X
new
(
n
)
-
X
¯
(
n
)
)
(
X
new
(
n
)
-
X
¯
(
n
)
)
T
,
where the first item of (23) is
(24)
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
+
X
¯
old
(
n
)
-
X
¯
(
n
)
)
×
(
X
i
(
n
)
-
X
¯
old
(
n
)
+
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
[
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
]
×
[
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
]
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
+
K
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
+
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
+
K
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
=
C
old
(
n
)
+
K
(
X
¯
old
(
n
)
-
K
X
¯
old
(
n
)
+
X
new
(
n
)
K
+
1
)
×
(
X
¯
old
(
n
)
-
K
X
¯
old
(
n
)
+
X
new
(
n
)
K
+
1
)
T
=
C
old
(
n
)
+
K
(
K
+
1
)
2
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
T
.
The second item of (23) is
(25)
(
X
new
(
n
)
-
X
¯
(
n
)
)
(
X
new
(
n
)
-
X
¯
(
n
)
)
T
=
(
X
new
(
n
)
-
X
¯
(
n
)
)
(
X
new
(
n
)
-
X
¯
(
n
)
)
T
=
(
X
new
(
n
)
-
K
X
¯
old
(
n
)
+
X
new
(
n
)
K
+
1
)
(
X
new
(
n
)
-
K
X
¯
old
(
n
)
+
X
new
(
n
)
K
+
1
)
T
=
K
2
(
K
+
1
)
2
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
T
.Consequently, the mode-n covariance matrix is updated as follows:
(26)
C
(
n
)
=
C
old
(
n
)
+
K
K
+
1
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
new
(
n
)
)
T
.
Therefore, when a new sample is added, the projective matrices are solved according to the eigen decomposition on (26).


## 3.2. Incremental Learning Based on Multiple Samples

Given an initial training datasetX
old
=
{
X
1
,
…
,
X
K
}, X
i
∈
ℝ
I
1
×
⋯
×
I
N, when new samples are added into training dataset, X
new
=
{
X
K
+
1
,
…
,
X
K
+
T
}, then training dataset becomes into X
=
{
X
1
,
…
,
X
K
,
X
K
+
1
,
…
,
X
K
+
T
}. In this case, the mean tensor is updated into the following:
(27)
X
¯
=
1
K
+
T
∑
i
=
1
K
+
T
X
i
=
1
K
+
T
(
∑
i
=
1
K
X
i
+
∑
i
=
K
+
1
K
+
T
X
i
)
=
1
K
+
T
(
K
X
¯
old
+
T
X
¯
new
)
.
Its mode-n covariance matrix is
(28)
C
(
n
)
=
∑
i
=
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
+
∑
i
=
K
+
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
.
The first item in (28) is written as follows:
(29)
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
+
K
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
+
∑
i
=
1
K
[
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
f
f
f
f
f
f
f
f
f
f
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
]
,
where
(30)
∑
i
=
1
K
[
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
f
f
f
+
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
]
=
K
X
¯
old
(
n
)
X
¯
old
(
n
)
T
-
K
X
¯
old
(
n
)
X
¯
(
n
)
T
-
K
X
¯
old
(
n
)
X
¯
old
(
n
)
T
+
K
X
¯
old
(
n
)
X
¯
(
n
)
T
+
K
X
¯
old
(
n
)
X
¯
old
(
n
)
T
-
K
X
¯
old
(
n
)
X
¯
old
(
n
)
T
-
K
X
¯
(
n
)
X
¯
old
(
n
)
T
+
K
X
¯
(
n
)
X
¯
old
(
n
)
T
=
0
,
K
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
(
n
)
)
T
=
K
T
2
(
K
+
T
)
2
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
.
Putting (30) into (29), then (29) becomes as follows:
(31)
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
C
old
(
n
)
+
K
T
2
(
K
+
T
)
2
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
.
The second item in (28) is written as follows:
(32)
∑
i
=
K
+
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
C
new
(
n
)
+
T
(
X
¯
new
(
n
)
-
X
¯
(
n
)
)
(
X
¯
new
(
n
)
-
X
¯
(
n
)
)
T
,
where
(33)
T
(
X
¯
new
(
n
)
-
X
¯
(
n
)
)
(
X
¯
new
(
n
)
-
X
¯
(
n
)
)
T
=
K
2
T
(
K
+
T
)
2
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
Then (32) becomes as follows:
(34)
∑
i
=
K
+
1
K
+
T
(
X
i
(
n
)
-
X
¯
(
n
)
)
(
X
i
(
n
)
-
X
¯
(
n
)
)
T
=
C
new
(
n
)
+
K
2
T
(
K
+
T
)
2
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
Putting (31) and (34) into (28), then we can get the following:
(35)
C
(
n
)
=
C
old
(
n
)
+
C
new
(
n
)
+
K
T
K
+
T
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
.
It is worthy to note that when new samples are available, it has no need to recompute the mode-n covariance matrix of all training samples. We just have to solve the mode-n covariance matrix of new added samples and the difference between original training samples and new added samples. However, like traditional incremental PCA, eigen decomposition on C
(
n
) has been repeated once new samples are added. It is certain that the repeated eigen decomposition on C
(
n
) will cause heavy computational cost, which is called “the eigen decomposition updating problem.” For traditional vector-based incremental learning algorithm, the updated-SVD technique is proposed in [25] to fit the eigen decomposition. This paper will introduce the updated-SVD technique into tensor-based incremental learning algorithm.For original samples, the mode-n covariance matrix is
(36)
C
old
(
n
)
=
∑
i
=
1
K
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
(
X
i
(
n
)
-
X
¯
old
(
n
)
)
T
=
S
old
(
n
)
S
old
(
n
)
T
,
where S
old
(
n
)
=
[
X
1
(
n
)
-
X
¯
old
(
n
)
,
…
,
X
K
(
n
)
-
X
¯
old
(
n
)
]. According to the eigen decomposition S
old
(
n
)
=
svd
(
U
Σ
V
T
), we can get the following:
(37)
S
old
(
n
)
S
old
(
n
)
T
=
(
U
Σ
V
T
)
(
U
Σ
V
T
)
T
=
U
Σ
V
T
V
Σ
U
T
=
U
Σ
2
U
T
=
eig
(
C
old
(
n
)
)
.
So it is easy to derive that the eigen-vector of C
old
(
n
) is the left singular vector of S
old
(
n
) and the eigen-values correspond to the extraction of left singular values of S
old
(
n
).For new samples, the mode-n covariance matrix is
(38)
C
new
(
n
)
=
∑
i
=
K
+
1
K
+
T
(
X
i
(
n
)
-
X
¯
new
(
n
)
)
(
X
i
(
n
)
-
X
¯
new
(
n
)
)
T
=
S
new
(
n
)
S
new
(
n
)
T
,
where S
new
(
n
)
=
[
X
1
(
n
)
-
X
¯
new
(
n
)
,
…
,
X
K
(
n
)
-
X
¯
new
(
n
)
]. According to (35), the updated mode-n covariance matrix is defined as follows:
(39)
C
(
n
)
=
C
old
(
n
)
+
C
new
(
n
)
+
K
T
K
+
T
×
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
T
=
S
(
n
)
S
(
n
)
T
,
where S
(
n
)
=
[
S
old
(
n
)
,
S
new
(
n
)
,
K
T
/
(
K
+
T
)
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
]. Therefore, the updated projective matrix U
(
n
) is the eigen-vectors corresponding to the largest P
n eigen-values of S
(
n
). The main steps of incremental tensor principal component analysis are listed as follows:input: original samples and new added samples,
output:N projective matrices.Step 1.
Computing and saving(40)
eig
(
C
old
(
n
)
)
≈
[
U
r
(
n
)
,
Σ
r
(
n
)
]
.Step 2.
Fori
=
1
:
N
(41)
B
=
[
S
new
(
n
)
,
K
T
K
+
T
(
X
¯
old
(
n
)
-
X
¯
new
(
n
)
)
]
.
Processing QR decomposition for the following equation:(42)
QR
=
(
I
-
U
r
(
n
)
U
r
(
n
)
T
)
B
.
Processing SVD decomposition for the following equation:(43)
svd
[
Σ
r
(
n
)
U
r
(
n
)
T
B
0
R
]
=
U
^
Σ
^
V
^
T
.
Computing the following equation:(44)
[
S
old
(
n
)
,
B
]
≈
(
[
U
r
(
n
)
,
Q
]
U
^
)
Σ
^
(
[
V
r
(
n
)
0
0
I
]
V
^
)
T
.
Then the updated projective matrix is computed as follows:(45)
U
(
n
)
=
[
U
r
(
n
)
,
Q
]
U
^
,
end.Step 3.
Repeating the above steps until the incremental learning is finished.


## 3.3. The Complexity Analysis

For tensor datasetX
=
{
X
1
,
…
,
X
M
}, X
i
∈
ℝ
I
1
×
⋯
×
I
N, without loss of generality, it is assumed that all dimensions are equal, that is, I
1
=
⋯
=
I
N
=
I.Vector-based PCA converts all data into vector and constructs a data matrixX
∈
ℝ
M
×
D, D
=
I
N. For vector-based PCA, the main computational cost contains three parts: the computation of the covariance matrix, the eigen decomposition of the covariance matrix, and the computation of low-dimensional features. The time complexity to compute covariance matrix is O
(
M
I
2
N
), the time complexity of the eigen decomposition is O
(
I
3
N
), and the time complexity to compute low-dimensional features is O
(
M
I
2
N
+
I
3
N
).Letting the iterative number be 1, the time complexity to computing the mode-n covariance matrix for MPCA is O
(
M
N
I
N
+
1
), the time complexity of eigen decomposition is O
(
N
I
3
), and the time complexity to compute low-dimensional features is O
(
M
N
I
N
+
1
), so the total time complexity is O
(
M
N
I
N
+
1
+
N
I
3
). Considering the time complexity, MPCA is superior to PCA.For ITPCA, it is assumed thatT incremental datasets are added; MPCA has to recompute mode-n covariance matrix and conducts eigen decomposition for initial dataset and incremental dataset. The more the training samples are, the higher time complexity they have. If updated-SVD is used, we only need to compute QR decomposition and SVD decomposition. The time complexity of QR decomposition is O
(
N
I
N
+
1
). The time complexity of the rank-k decomposition of the matrix with the size of (
r
+
I
)
×
(
r
+
I
N
-
1
) is O
(
N
(
r
+
I
)
k
2
). It can be seen that the time complexity of updated-SVD has nothing to do with the number of new added samples.Taking the space complexity into account, if training samples are reduced into low-dimensional space and the dimension isD
=
∏
n
=
1
N
d
n, then PCA needs D
∏
n
=
1
N
I
n bytes to save projective matrices and MPCA needs ∑
n
=
1
N
I
n
d
n bytes. So MPCA has lower space complexity than PCA. For incremental learning, both PCA and MPCA need M
∏
n
=
1
N
I
n bytes to save initial training samples; ITPCA only need ∑
n
=
1
N
I
n
2 bytes to keep mode-n covariance matrix.


## 4. Experiments

In this section, the handwritten digit recognition experiments on the USPS image dataset are conducted to evaluate the performance of incremental tensor principal component analysis. The USPS handwritten digit dataset has 9298 images from zero to nine shown in Figure1. For each image, the size is 16
×
16. In this paper, we choose 1000 images and divide them into initial training samples, new added samples, and test samples. Furthermore, the nearest neighbor classifier is employed to classify the low-dimensional features. The recognition results are compared with PCA [26], IPCA [15], and MPCA [11].Figure 1
The samples in USPS dataset.At first, we choose 70 samples belonging to four classes from initial training samples. For each time of incremental learning, 70 samples which belong to the other two classes are added. So after three times, the class labels of the training samples are ten and there are 70 samples in each class. The resting samples of original training samples are considered as testing dataset. All algorithms are implemented in MATLAB 2010 on an Intel (R) Core (TM) i5-3210 M CPU @ 2.5 GHz with 4 G RAM.Firstly, 36 PCs are preserved and fed into the nearest neighbor classifier to obtain the recognition results. The results are plotted in Figure2. It can be seen that MPCA and ITPCA are better than PCA and IPCA for initial learning; the probable reason is that MPCA and ITPCA employ tensor representation to preserve the structure information.Figure 2
The recognition results for 36 PCs of the initial learning.The recognition results under different learning stages are shown in Figures3, 4, and 5. It can be seen that the recognition results of these four methods always fluctuate violently when the numbers of low-dimensional features are small. However, with the increment of the feature number, the recognition performance keeps stable. Generally MPCA and ITPCA are superior to PCA and IPCA. Although ITPCA have comparative performance at first two learning, ITPCA begin to surmount MPCA after the third learning. Figure 6 has given the best recognition percents of different methods. We can get the same conclusion as shown in Figures 3, 4, and 5.Figure 3
The recognition results of different methods of the first incremental learning.Figure 4
The recognition results of different methods of the second incremental learning.Figure 5
The recognition results of different methods of the third incremental learning.Figure 6
The comparison of recognition performance of different methods.The time and space complexity of different methods are shown in Figures7 and 8, respectively. Taking the time complexity into account, it can be found that at the stage of initial learning, PCA has the lowest time complexity. With the increment of new samples, the time complexity of PCA and MPCA grows greatly and the time complexity of IPCA and ITPCA becomes stable. ITPCA has slower increment than MPCA. The reason is that ITPCA introduces incremental learning based on the updated-SVD technique and avoids decomposing the mode-n covariance matrix of original samples again. Considering the space complexity, it is easy to find that ITPCA has the lowest space complexity among four compared methods.Figure 7
The comparison of time complexity of different methods.Figure 8
The comparison of space complexity of different methods.


## 5. Conclusion

This paper presents incremental tensor principal component analysis based on updated-SVD technique to take full advantage of redundancy of the space structure information and online learning. Furthermore, this paper proves that PCA and 2DPCA are the special cases of MPCA and all of them can be unified into the graph embedding framework. This paper also analyzes incremental learning based on single sample and multiple samples in detail. The experiments on handwritten digit recognition have demonstrated that principal component analysis based on tensor representation is superior to tensor principal component analysis based on vector representation. Although at the stage of initial learning, MPCA has better recognition performance than ITPCA, the learning capability of ITPCA becomes well gradually and exceeds MPCA. Moreover, even if new samples are added, the time and space complexity of ITPCA still keep slower increment.



---

*Source: 819758-2014-01-30.xml*