# Incremental Graph Regulated Nonnegative Matrix Factorization for Face Recognition

Authors: Zhe-Zhou Yu; Yu-Hao Liu; Bin Li; Shu-Chao Pang; Cheng-Cheng Jia
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

In a real world application, we seldom get all images at one time. Considering this case, if a company hired an employee, all his images information needs to be recorded into the system; if we rerun the face recognition algorithm, it will be time consuming. To address this problem, In this paper, firstly, we proposed a novel subspace incremental method called incremental graph regularized nonnegative matrix factorization (IGNMF) algorithm which imposes manifold into incremental nonnegative matrix factorization algorithm  (INMF); thus, our new algorithm is able to preserve the geometric structure in the data under incremental study framework; secondly, considering we always get many face images belonging to one person or many different people as a batch, we improved our IGNMF algorithms to Batch-IGNMF algorithms (B-IGNMF), which implements incremental study in batches. Experiments show that (1) the recognition rate of our IGNMF and B-IGNMF algorithms is close to GNMF algorithm while it runs faster than GNMF. (2) The running times of our IGNMF and B-IGNMF algorithms are close to INMF while the recognition rate outperforms INMF. (3) Comparing with other popular NMF-based face recognition incremental algorithms, our IGNMF and B-IGNMF also outperform then both the recognition rate and the running time.


---

## Body

## 1. Introduction

Nonnegative matrix factorization (NMF) is a widely used method for low-rank approximation of a nonnegative matrix (matrix with only nonnegative entries), where nonnegative constraints are imposed on factor matrices in the decomposition. There are large bodies of past work on NMF [1]. Lee and Seung [2, 3] proposed NMF for learning parts of faces, and in their work the reconstruction error function F(U,V) is introduced: F(U,V)=∥X-UV∥F2, where X denotes the data matrix, U can be considered as the basic matrix, and V can be considered as the coefficient matrix; all elements of X, U, and V are nonnegative. Sparse coding is a famous parts-based representation method, by minimizing a L1 regularization-related objective function of NMF-based algorithms, sparse constraints can be achieved. Hoyer [4] proposed a method by keeping L2 norm unchanged in each iteration, but L1 norm set to achieve desired sparseness. Li et al. [5] proposed another sparse representation method which focused on sparse NMF algorithm with Kullback-Leibler based cost function. Discrimination method was also introduced into NMF algorithm. Wang et al. [6] proposed a Fisher nonnegative matrix factorization which introduces Fisher constraint (discrimination) method into NMF algorithm. later, Nikitidis et al. [7] introduced subclass discriminant into NMF algorithm, by separating each class into several subclasses; this method was able to ensure that the underlying data distribution in each subclass is unimodal. Because the convergence of canonical NMF algorithms is slow, gradient descent based methods are introduced to NMF to improve its speed of convergence. Guan et. al [8] applied Nesterov’s optimal gradient method to alternatively optimize one factor with another. By introducing fast gradient descent method into search of the optimal step size for gradient descent based NMF algorithm, Guan et al. [9] introduced nonnegative patch alignment framework (NPAF) and nonnegative discriminative locality alignment (NDLA). Canonical NMF algorithm aims to minimize the Euclidean distance or the Kullback-Leibler distance between the data matrix X and its reconstruction matrix U×V. By introducing Manhattan distance into NMF algorithm, Guan et al. [10] introduced Manhattan nonnegative matrix factorization (MahNMF), then rank-one residual iteration method and Nesterov’s smoothing method are both introduced to optimizing MahNMF. The geometrical information of the original data space is an important information for face recognition. Zhang et al. [11] proposed a novel topology preserving nonnegative matrix factorization (TPNMF) which considers the gradient distance instead of the Euclidean distance or the Kullback-Leibler distance. By constructing the intrinsic and penalty graphs, Liu et al. [12] proposed the projective nonnegative graph embedding (PNGE). Cai et al. [13] proposed graph regularized nonnegative matrix factorization (GNMF) algorithm for face recognition. GNMF imposes manifold into NMF, which makes it able to preserve geometric structure of data after it maps the original image into low dimension space.NMF-based algorithms are notoriously slow to converge. In practice, if new image comes, algorithm needs to rerun which is time consuming. To address this problem, incremental process used for online study has attracted a lot of attention. During an incremental study process of NMF, once a factorization, such asU and V which mentioned above, is obtained for a group of face images, the representation of U should be updated with a small computational cost, but the canonical NMF and many other algorithms are too expensive to compute U and V every time when new face image comes. Bucak and Gunsel [14] introduced an Incremental nonnegative matrix factorization algorithm (INMF), which imposes NMF into incremental study. This makes it possible to represent data content online and reduce dimension significantly. Chen et al. [15] proposed another incremental nonnegative matrix factorization (INMF) for face representation and recognition. In order to distinguish Chen’s algorithms [15] from Bucak and Gunsel’s [14], we called Chen’s algorithms CINMF. There are two main differences between CINMF and INMF: first, INMF is an unsupervised method while CINMF is a supervised method; second, INMF can only deal with one new image while CINMF can only deal with a batch of images which belong to a new class. Wang and Lu [16] introduced an incremental orthogonal projective nonnegative matrix factorization algorithm (IOPNMF) which introduced orthogonal projective constraint into incremental NMF. Lefèvre et al. [17] introduced incremental study into Itakura-Saito NMF algorithm; the Istakura-Saito divergence was defined as dIS(y,x)=∑i‍(yi/xi-log⁡yi/xi-1). The proposed algorithm is used in the field of audio source separation. Guan et al. [18] proposed an efficient online RSA-NMF algorithm. RSA-NMF is a NMF algorithm based which introduces Robust Stochastic approximation (RSA) to optimize NMF algorithm. Benefiting from the smartly chosen learnig rate and averaging technique, online RSA-NMF algorithm converges at the rate of O(1/k) in each update of the bases. later Guan et al. also gave some extensions on the proposed online RSA-NMF algorithm. Cao et al. [19] introduced an online NMF algorithm. Once we get the factorization of X as U×V, by separating the new data matrix X, and the new coefficient matrix V into two corresponding parts, the inequation can be rewritten as [Xx]≈U′×[V′v]; every iteration, [V′v], can be recomputed with a small computation cost while U′ can be recomputed as U′=U×(V′)-1; obviously there is an assumption that X≈U×V are full-rank decompositions and V′ is invertible.Although the incremental algorithms we mentioned above dramatically reduce the cost of incremental study, they did not consider the geometrical information of the original data space on the original manifold. The geometrical information of the original data space is an important information for face recognition [20, 21]. Data set often lay in a high dimension manifold, so the intrinsic geodesic distance in the manifold between two data points is more suitable than Euclidean distance. Thus, in this paper, By introducing manifold into Incremental nonnegative matrix factorization algorithm (INMF), first, we propose a new incremental study algorithm called incremental graph regulated nonnegative matrix factorization (IGNMF). Second, as human face images always come in batches, we improve our IGNMF algorithms to Batch-IGNMF algorithms (B-IGNMF). The contributions of the research presented in this paper are as follows.(1)
We propose a novel subspace incremental method called incremental graph regularized nonnegative matrix factorization algorithm (IGNMF), which is able to preserve discrimination information under incremental study framework.(2)
We further improve our IGNMF algorithms, thus developing Batch-IGNMF (B-IGNMF), which is able to perform incremental study with image batches no mater whether the batch of images belongs to the same class or different classes.The remainder of this paper is organized as follows. Section2 introduces the GNMF algorithm and INMF algorithm. Section 3 presents our IGNMF and B-IGNMF algorithms. Experiments on face databases are reported in Section 4. Section 5 concludes the paper.


## 2. A Brief Review of GNMF and INMF

In this section, we will give a brief review on graph regularized nonnegative matrix factorization (GNMF) which was proposed by Cai et al. [13] and incremental nonnegative matrix factorization algorithm (INMF) which was proposed by Bucak and Gunsel [14]; both algorithms are closely related to our new proposed algorithms.


### 2.1. GNMF

The geometrical information of the original data space is an important information for face recognition [20, 21]; data set often lay in a high dimension manifold, so the intrinsic geodesic distance in the manifold between two data points is more suitable than Euclidean distance. Thus in this section, we will give a brief review on graph regularized NMF (GNMF) [13].Given a data matrixX=[x1,x2,…,xk]∈Rn×k, there are total k face image vectors and xi(1⩽i⩽k) denotes a vector of n-dimensional facial image, U∈Rn×r and V∈Rr×k, so the objective function F(U,V) for GNMF is defined as (1); by minimizing F(U,V) a factorization, U and V in GNMF, is obtained:
(1)F=∥X-UV∥F2+λTr⁡(VLVT).In the above equationF=∥·∥F2 denotes the matrix Frobenius norm [2]; Tr⁡(·) denotes the trace of a matrix; λ>0 is the regularization parameter; L is called graph Laplacian [22]; L=D-W, where W is the weight matrix, Wij=1 if xi∈Np(xj), and D is a diagonal matrix and Dii=∑j‍Wij. There are two methods to define W [13, 22].(1)
Supervised method is achieved by definingxi∈Np(xj) if xi and xj belong to the same class.(2)
Unsupervised method is achieved by definingNp(xi) as the set of p nearest neighbors of xi under the Euclidean distance.The iterative update algorithm proposed by Cai et al. [13] is as follows (2):
(2)Uijt+1=Uijt·(XVT)ij(UVVT)ijVijt+1=Vijt·(UTX+λVW)ij(VTUTU+λVD)ij,
where Uij and Vij are the elements of U and V, respectively.


### 2.2. INMF

Incremental nonnegative factorization (INMF) [14] is a popular incremental study algorithm which is NMF-based. Considering the canonical reconstruction inequation of NMF algorithm as X≈U×V, and each column of both sides is Xi≈U×Vi; from this inequation we can find that if we consider each column of the matrix U as the building block of the database and Vi can be considered as the reconstruction coefficient matrix, by summing each building block of U under the coefficient matrix Vi, original image Xi will be approximately reconstructed [2, 3].Every time when new imagex comes, the inequation of the reconstruction function will become [Xx]≈U×[Vv]; by assuming that the previous coefficient matrix V would not change during the incremental process, the computation cost will be reduced significantly.If we defined theFk as the cost function corresponding to the NMF as (3) where k denotes the total number of samples before incremental study, then
(3)Fk=∥X-UV∥2=∑i=1n‍∑j=1k‍[(Xk)ij-(UkVk)ij]2.Everytime, when the(k+1)th sample x arrives, the corresponding cost function Fk+1 can be defined as (4)
(4)Fk+1=∑i=1n‍∑j=1k+1‍[(Xk+1)ij-(Uk+1Vk+1)ij]2.NoteFk+1 can be separated into two parts as follows:
(5)Fk+1=∑i=1n‍∑j=1k+1‍[(Xk+1)ij-(Uk+1Vk+1)ij]2=∑i=1n‍∑j=1k‍[(Xk+1)ij-(Uk+1Vk+1)ij]2+∑i=1n‍[x-(Uk+1v)i,k+1]2,
where x and v can be considered as the new coming image and its corresponding coefficient vector. By assuming that the first k columns of Vk+1 would not change after the incremental study, the first part of (5) can be rewritten as
(6)∑i=1n‍∑j=1k‍[(Xk+1)ij-(Uk+1Vk+1)ij]2≈Fk=∑i=1n‍∑j=1k‍[(Xk)ij-(UkVk)ij]2.
So Fk+1 can be rewritten as
(7)Fk+1=Fk+∑i=1n‍[x-(Uk+1v)i,k+1]2=Fk+f.Considering thatFk is the function which is independent of vi, the partial derivative of ∂Fk/vi=0. Thus the partial derivative of ∂Fk+1/vi(=∂f/vi) and ∂Fk+1/Uij can be deduced. Then the update rule of vi and Uij can be formulated within the framework of gradient descent algorithm.In order to save space, here we just list the iterative update algorithms of INMF in (8):
(8)vi′⟵vi·(Uk+1Tx)i(Uk+1TUk+1v)i,(Uk+1′)ia⟵(Uk+1)ia·(XkVkT+Xk+1vT)ia(Uk+1UkVkT+Uk+1vvT)ia.


## 2.1. GNMF

The geometrical information of the original data space is an important information for face recognition [20, 21]; data set often lay in a high dimension manifold, so the intrinsic geodesic distance in the manifold between two data points is more suitable than Euclidean distance. Thus in this section, we will give a brief review on graph regularized NMF (GNMF) [13].Given a data matrixX=[x1,x2,…,xk]∈Rn×k, there are total k face image vectors and xi(1⩽i⩽k) denotes a vector of n-dimensional facial image, U∈Rn×r and V∈Rr×k, so the objective function F(U,V) for GNMF is defined as (1); by minimizing F(U,V) a factorization, U and V in GNMF, is obtained:
(1)F=∥X-UV∥F2+λTr⁡(VLVT).In the above equationF=∥·∥F2 denotes the matrix Frobenius norm [2]; Tr⁡(·) denotes the trace of a matrix; λ>0 is the regularization parameter; L is called graph Laplacian [22]; L=D-W, where W is the weight matrix, Wij=1 if xi∈Np(xj), and D is a diagonal matrix and Dii=∑j‍Wij. There are two methods to define W [13, 22].(1)
Supervised method is achieved by definingxi∈Np(xj) if xi and xj belong to the same class.(2)
Unsupervised method is achieved by definingNp(xi) as the set of p nearest neighbors of xi under the Euclidean distance.The iterative update algorithm proposed by Cai et al. [13] is as follows (2):
(2)Uijt+1=Uijt·(XVT)ij(UVVT)ijVijt+1=Vijt·(UTX+λVW)ij(VTUTU+λVD)ij,
where Uij and Vij are the elements of U and V, respectively.


## 2.2. INMF

Incremental nonnegative factorization (INMF) [14] is a popular incremental study algorithm which is NMF-based. Considering the canonical reconstruction inequation of NMF algorithm as X≈U×V, and each column of both sides is Xi≈U×Vi; from this inequation we can find that if we consider each column of the matrix U as the building block of the database and Vi can be considered as the reconstruction coefficient matrix, by summing each building block of U under the coefficient matrix Vi, original image Xi will be approximately reconstructed [2, 3].Every time when new imagex comes, the inequation of the reconstruction function will become [Xx]≈U×[Vv]; by assuming that the previous coefficient matrix V would not change during the incremental process, the computation cost will be reduced significantly.If we defined theFk as the cost function corresponding to the NMF as (3) where k denotes the total number of samples before incremental study, then
(3)Fk=∥X-UV∥2=∑i=1n‍∑j=1k‍[(Xk)ij-(UkVk)ij]2.Everytime, when the(k+1)th sample x arrives, the corresponding cost function Fk+1 can be defined as (4)
(4)Fk+1=∑i=1n‍∑j=1k+1‍[(Xk+1)ij-(Uk+1Vk+1)ij]2.NoteFk+1 can be separated into two parts as follows:
(5)Fk+1=∑i=1n‍∑j=1k+1‍[(Xk+1)ij-(Uk+1Vk+1)ij]2=∑i=1n‍∑j=1k‍[(Xk+1)ij-(Uk+1Vk+1)ij]2+∑i=1n‍[x-(Uk+1v)i,k+1]2,
where x and v can be considered as the new coming image and its corresponding coefficient vector. By assuming that the first k columns of Vk+1 would not change after the incremental study, the first part of (5) can be rewritten as
(6)∑i=1n‍∑j=1k‍[(Xk+1)ij-(Uk+1Vk+1)ij]2≈Fk=∑i=1n‍∑j=1k‍[(Xk)ij-(UkVk)ij]2.
So Fk+1 can be rewritten as
(7)Fk+1=Fk+∑i=1n‍[x-(Uk+1v)i,k+1]2=Fk+f.Considering thatFk is the function which is independent of vi, the partial derivative of ∂Fk/vi=0. Thus the partial derivative of ∂Fk+1/vi(=∂f/vi) and ∂Fk+1/Uij can be deduced. Then the update rule of vi and Uij can be formulated within the framework of gradient descent algorithm.In order to save space, here we just list the iterative update algorithms of INMF in (8):
(8)vi′⟵vi·(Uk+1Tx)i(Uk+1TUk+1v)i,(Uk+1′)ia⟵(Uk+1)ia·(XkVkT+Xk+1vT)ia(Uk+1UkVkT+Uk+1vvT)ia.


## 3. IGNMF and B-IGNMF

Bucak and Gunsel [14] introduced an incremental nonnegative matrix factorization algorithm (INMF) which imposed the NMF algorithm into incremental study, so INMF inherits the disadvantage of the NMF algorithm; that is, it does not consider the geometric structure in the data. In this section, we introduced an incremental graph regularized nonnegative matrix factorization algorithm (IGNMF), in which manifold is introduced to overcome this limitation.


### 3.1. IGNMF

LetXk, Uk, Vk, Lk, and Fk denote the corresponding X, U, V, L, and F(U,V) in (1) under the initial k samples, so the objective function Fk can be rewriten as
(9)Fk=∑i=1n‍∑j=1k‍[(Xk)ij-(UkVk)ij]2+λTr⁡(VkLkVkT).LetXk+1, Uk+1, Vk+1, Lk+1, and Fk+1 denote the corresponding X, U, V, L, and F(U,V) in (1) when the (k+1)th sample arrives. So objective function Fk+1 can be rewriten as
(10)Fk+1=∑i=1n‍∑j=1k+1‍[(Xk+1)ij-(Uk+1Vk+1)ij]2+λTr⁡(Vk+1Lk+1Vk+1T).U can be considered as the basic matrix and V can be considered as the coefficient matrix, so the reconstruction process can be thought as adding columns of matrix U under the coefficient matrix Vi, just as Xi≈U×Vi [3]. Thus we make the assumption that during the incremental process, when the (k+1)th sample arrives, the first k columns of Vk+1 does not change, which means the fist k columns of Vk+1 is approximately equal to Vk. This assumption would reduce the computation cost significantly. Experiments show that IGNMF would iterate less than 5 times and then the objective function converges to its minimal value, because we just need to update the last column of Vk+1 meanwhile Uk+1 needs to be updated completely which will dramatically reduce the cost of incremental study. For more details about this assumption, please refer to [14].AssumingFk+1k refers to the objective function corresponding to GNMF representation of the first k sample when the (k+1)th sample arrives, Lk+1k refers to the k×k dimensional matrix which equals the first k rows and first k columns of Lk+1, and r is a predefined parameter which indicates that the n-dimensional facial image vector maps in to an r-dimensional vector. So Fk+1k can be rewritten as
(11)Fk+1k=∑i=1n‍∑j=1k‍[Xij-(Uk+1Vk+1)ij]2+λ∑l=1r‍∑i=1k‍∑j=1k‍(Vk+1)li(Lk+1k)ij(Vk+1T)jl≈∑i=1n‍∑j=1k‍[Xij-(Uk+1Vk)ij]2+λ∑l=1r‍∑i=1k‍∑j=1k‍(Vk)li(Lk+1k)ij(VkT)jl.Consequently, objective functionFk+1 can be rewriten as follows:
(12)Fk+1=∑i=1n‍∑j=1k+1‍[Xij-(Uk+1Vk+1)ij]2+λ∑l=1r‍∑i=1k+1‍∑j=1k+1‍(Vk+1)li(Lk+1)ij(Vk+1T)jl≈∑i=1n‍∑j=1k‍[Xij-(Uk+1Vk)ij]2+λ∑l=1r‍∑i=1k‍∑j=1k‍(Vk)li(Lk+1k)ij(VkT)jl+∑i=1n‍[x-(Uk+1v)i]2+λ∑l=1r‍{v2(Lk+1)k+1,k+1+∑j=1k‍[2v(Vk)lj(Lk+1)j,k+1]}=Fk+1k+fk+1,
where x means the new coming facial vector and v means the coefficient vector corresponding to x.After constructing the objective function given by (12), gradient descent optimization that yields IGNMF can be performed. The update rule of v can be formulated within the framework of gradient descent algorithm as follows:
(13)va′⟵va-μa·∂Fk+1∂va.In (13), ∂Fk+1/∂va is the partial derivative of Fk+1 with respect to va and ∂Fk+1/∂va=∂Fk+1k/∂va+∂fk+1/∂va, because Fk+1k is the function which is not relevant to va, so ∂Fk+1k/∂va=0, and we just need to compute the partial derivative of fk+1:(14)∂Fk+1∂va=∂Fk+1k∂va+∂fk+1∂va=∂∂va{∑i=1n‍[x-(Uk+1v)i]2+λ∑l=1r‍[v2(Lk+1)k+1,k+1+∑j=1k‍[2v(Vk)lj(Lk+1)j,k+1+(Vk)j,k+12(Wk+1)l,k+1]]}=2[-Uk+1Tx+Uk+1TUk+1v+λv(Lk+1)k+1,:]a.μ
a is the step size and is calculated by
(15)μa=va2[Uk+1TUk+1v+λ·v(Dk+1)k+1,:]a,
where (Lk+1)k+1,:, (Dk+1)k+1,: and (Wk+1)k+1,: are vectors which are equal to the (k+1)th row of Lk+1, Dk+1 and Dk+1, respectively.After substituting (14) and (15) into (13), The update rule equation for va yields as
(16)va′⟵va·[Uk+1Tx+λ·v(Wk+1)k+1,:]a[Uk+1TUk+1v+λ·v(Dk+1)k+1,:]a.The update rule of(Uk+1)ia can also be formulated within the framework of gradient descent algorithm as
(17)(Uk+1′)ia⟵(Uk+1)ia-ηia·∂Fk+1∂(Uk+1)ia.
In (17), ∂Fk+1/∂(Uk+1)ia is the partial derivative of Fk+1 with respect to (Uk+1)ia and is given as
(18)∂Fk+1∂(Uk+1)ia=∂∂(Uk+1)ia{∑i=1n‍∑j=1k+1‍[Xij-(Uk+1Vk+1)ij]2vvvvvvvvvvvvvv+λ∑l=1r‍∑i=1k+1‍∑j=1k+1‍(Vk+1)li(Lk+1)ij(Vk+1T)jl}=∂∂(Uk+1)ia∑i=1n‍∑j=1k+1‍[Xij-(Uk+1Vk+1)ij]2=2∑j=1k+1‍[-Xij(Uk+1)aj+(Vk+1)aj(Uk+1Vk+1)ij].η is the step size and is calculated by
(19)ηia=(Uk+1)ia2∑j=1k+1(Uk+1Vk+1)ijVjaT.
After substituting (18) and (19) into (17), The update rule equation for (Uk+1)ia yields as
(20)(Uk+1′)ia⟵(Uk+1)ia·(XkVkT+Xk+1vT)ia(Uk+1UkVkT+Uk+1vvT)ia.We omit the proof of its convergence as it is similar to that of GNMF while IGNMF just assumes the firstk columns of V would not be updated during iterations.


### 3.2. Batch-IGNMF

In practice, images often come in batches. For example, a face recognition system needs to record a batch of images belonging to a new class or belonging to many different classes.Once several images come, our IGNMF needs to run one time for each image, which is time consuming if there are too many images. In this section, we propose an improved version of IGNMF algorithm which can deal with a batch of images. This improved version is named Batch-IGNMF (B-IGNMF), which is able to perform incremental study in batch of images no matter whether the batch of images belongs to the same class or different classes.LetXl denote the new coming l images. So Xk+l is the total sample with its first k columns equal to Xk and the rest l columns equal to Xl. Uk+l and Vk+l denote the optimized factor matrices of Xk+l, assuming Vk as the first k columns of Vk+l which would not change during incremental study, Vl is the last l columns of Vk+l denoting the corresponding coefficient matrix of Xl, and (Wk+l)k+1~k+l,: denotes the rows of Wk+l from k+1 to k+l.So the objective functionFk+l can be rewriten as
(21)Fk+l=∑i=1n‍∑j=1k+l‍[Xij-(Uk+lVk+l)ij]2+λTr⁡(Vk+lLk+lVk+lT).
We omit the detailed derivation process due to its similarity to the derivation process of IGNMF. We just list the multiplicative update rules as
(22)(Vl′)ia⟵(Vl)ia·[Uk+1TXl+λ·Vk+l(Wk+l)k+l~k+l,:]ia[Uk+lTUk+lVl+λ·Vk+l(Dk+l)k+l~k+l,:]ia,(Uk+l′)ia⟵(Uk+l)ia·(XkVkT+XlVlT)ia(Uk+lUkVkT+Uk+lVlVlT)ia.


## 3.1. IGNMF

LetXk, Uk, Vk, Lk, and Fk denote the corresponding X, U, V, L, and F(U,V) in (1) under the initial k samples, so the objective function Fk can be rewriten as
(9)Fk=∑i=1n‍∑j=1k‍[(Xk)ij-(UkVk)ij]2+λTr⁡(VkLkVkT).LetXk+1, Uk+1, Vk+1, Lk+1, and Fk+1 denote the corresponding X, U, V, L, and F(U,V) in (1) when the (k+1)th sample arrives. So objective function Fk+1 can be rewriten as
(10)Fk+1=∑i=1n‍∑j=1k+1‍[(Xk+1)ij-(Uk+1Vk+1)ij]2+λTr⁡(Vk+1Lk+1Vk+1T).U can be considered as the basic matrix and V can be considered as the coefficient matrix, so the reconstruction process can be thought as adding columns of matrix U under the coefficient matrix Vi, just as Xi≈U×Vi [3]. Thus we make the assumption that during the incremental process, when the (k+1)th sample arrives, the first k columns of Vk+1 does not change, which means the fist k columns of Vk+1 is approximately equal to Vk. This assumption would reduce the computation cost significantly. Experiments show that IGNMF would iterate less than 5 times and then the objective function converges to its minimal value, because we just need to update the last column of Vk+1 meanwhile Uk+1 needs to be updated completely which will dramatically reduce the cost of incremental study. For more details about this assumption, please refer to [14].AssumingFk+1k refers to the objective function corresponding to GNMF representation of the first k sample when the (k+1)th sample arrives, Lk+1k refers to the k×k dimensional matrix which equals the first k rows and first k columns of Lk+1, and r is a predefined parameter which indicates that the n-dimensional facial image vector maps in to an r-dimensional vector. So Fk+1k can be rewritten as
(11)Fk+1k=∑i=1n‍∑j=1k‍[Xij-(Uk+1Vk+1)ij]2+λ∑l=1r‍∑i=1k‍∑j=1k‍(Vk+1)li(Lk+1k)ij(Vk+1T)jl≈∑i=1n‍∑j=1k‍[Xij-(Uk+1Vk)ij]2+λ∑l=1r‍∑i=1k‍∑j=1k‍(Vk)li(Lk+1k)ij(VkT)jl.Consequently, objective functionFk+1 can be rewriten as follows:
(12)Fk+1=∑i=1n‍∑j=1k+1‍[Xij-(Uk+1Vk+1)ij]2+λ∑l=1r‍∑i=1k+1‍∑j=1k+1‍(Vk+1)li(Lk+1)ij(Vk+1T)jl≈∑i=1n‍∑j=1k‍[Xij-(Uk+1Vk)ij]2+λ∑l=1r‍∑i=1k‍∑j=1k‍(Vk)li(Lk+1k)ij(VkT)jl+∑i=1n‍[x-(Uk+1v)i]2+λ∑l=1r‍{v2(Lk+1)k+1,k+1+∑j=1k‍[2v(Vk)lj(Lk+1)j,k+1]}=Fk+1k+fk+1,
where x means the new coming facial vector and v means the coefficient vector corresponding to x.After constructing the objective function given by (12), gradient descent optimization that yields IGNMF can be performed. The update rule of v can be formulated within the framework of gradient descent algorithm as follows:
(13)va′⟵va-μa·∂Fk+1∂va.In (13), ∂Fk+1/∂va is the partial derivative of Fk+1 with respect to va and ∂Fk+1/∂va=∂Fk+1k/∂va+∂fk+1/∂va, because Fk+1k is the function which is not relevant to va, so ∂Fk+1k/∂va=0, and we just need to compute the partial derivative of fk+1:(14)∂Fk+1∂va=∂Fk+1k∂va+∂fk+1∂va=∂∂va{∑i=1n‍[x-(Uk+1v)i]2+λ∑l=1r‍[v2(Lk+1)k+1,k+1+∑j=1k‍[2v(Vk)lj(Lk+1)j,k+1+(Vk)j,k+12(Wk+1)l,k+1]]}=2[-Uk+1Tx+Uk+1TUk+1v+λv(Lk+1)k+1,:]a.μ
a is the step size and is calculated by
(15)μa=va2[Uk+1TUk+1v+λ·v(Dk+1)k+1,:]a,
where (Lk+1)k+1,:, (Dk+1)k+1,: and (Wk+1)k+1,: are vectors which are equal to the (k+1)th row of Lk+1, Dk+1 and Dk+1, respectively.After substituting (14) and (15) into (13), The update rule equation for va yields as
(16)va′⟵va·[Uk+1Tx+λ·v(Wk+1)k+1,:]a[Uk+1TUk+1v+λ·v(Dk+1)k+1,:]a.The update rule of(Uk+1)ia can also be formulated within the framework of gradient descent algorithm as
(17)(Uk+1′)ia⟵(Uk+1)ia-ηia·∂Fk+1∂(Uk+1)ia.
In (17), ∂Fk+1/∂(Uk+1)ia is the partial derivative of Fk+1 with respect to (Uk+1)ia and is given as
(18)∂Fk+1∂(Uk+1)ia=∂∂(Uk+1)ia{∑i=1n‍∑j=1k+1‍[Xij-(Uk+1Vk+1)ij]2vvvvvvvvvvvvvv+λ∑l=1r‍∑i=1k+1‍∑j=1k+1‍(Vk+1)li(Lk+1)ij(Vk+1T)jl}=∂∂(Uk+1)ia∑i=1n‍∑j=1k+1‍[Xij-(Uk+1Vk+1)ij]2=2∑j=1k+1‍[-Xij(Uk+1)aj+(Vk+1)aj(Uk+1Vk+1)ij].η is the step size and is calculated by
(19)ηia=(Uk+1)ia2∑j=1k+1(Uk+1Vk+1)ijVjaT.
After substituting (18) and (19) into (17), The update rule equation for (Uk+1)ia yields as
(20)(Uk+1′)ia⟵(Uk+1)ia·(XkVkT+Xk+1vT)ia(Uk+1UkVkT+Uk+1vvT)ia.We omit the proof of its convergence as it is similar to that of GNMF while IGNMF just assumes the firstk columns of V would not be updated during iterations.


## 3.2. Batch-IGNMF

In practice, images often come in batches. For example, a face recognition system needs to record a batch of images belonging to a new class or belonging to many different classes.Once several images come, our IGNMF needs to run one time for each image, which is time consuming if there are too many images. In this section, we propose an improved version of IGNMF algorithm which can deal with a batch of images. This improved version is named Batch-IGNMF (B-IGNMF), which is able to perform incremental study in batch of images no matter whether the batch of images belongs to the same class or different classes.LetXl denote the new coming l images. So Xk+l is the total sample with its first k columns equal to Xk and the rest l columns equal to Xl. Uk+l and Vk+l denote the optimized factor matrices of Xk+l, assuming Vk as the first k columns of Vk+l which would not change during incremental study, Vl is the last l columns of Vk+l denoting the corresponding coefficient matrix of Xl, and (Wk+l)k+1~k+l,: denotes the rows of Wk+l from k+1 to k+l.So the objective functionFk+l can be rewriten as
(21)Fk+l=∑i=1n‍∑j=1k+l‍[Xij-(Uk+lVk+l)ij]2+λTr⁡(Vk+lLk+lVk+lT).
We omit the detailed derivation process due to its similarity to the derivation process of IGNMF. We just list the multiplicative update rules as
(22)(Vl′)ia⟵(Vl)ia·[Uk+1TXl+λ·Vk+l(Wk+l)k+l~k+l,:]ia[Uk+lTUk+lVl+λ·Vk+l(Dk+l)k+l~k+l,:]ia,(Uk+l′)ia⟵(Uk+l)ia·(XkVkT+XlVlT)ia(Uk+lUkVkT+Uk+lVlVlT)ia.


## 4. Experiments

In this section, the FERET database [23, 24] and CMU-PIE database [25] are selected to evaluate the performance of our IGNMF and B-IGNMF algorithms, along with two canonical face recognition algorithms: supervised GNMF (GNMF-S) and unsupervised GNMF (GNMF-U) and three incremental algorithms: INMF, CINMF, and IOPNMF. NMF is selected as the baseline. The stopping condition of iterative update is defined as (23) in all experiments:
(23)F(n-1)-F(n)F(n)<δ,
where F(n) is the nth iteration of the update criterion function defined in (9) under the nth iteration.In the FERET database [23, 24], we select 200 individual faces (7 images for each). All images in the database are aligned by the centers of eyes and mouth and then resized into 25×25. The CMU-PIE database includes total of 68 individuals [25] and we select all these 68 individuals, each of which has 56 images, including 7 poses with neural expression in different views and 38 different lighting conditions and 11 talking images in frontal view. All images in the database are aligned by the centers of eyes and mouth and then resized into 28×23. Examples of these two datasets are shown in Figures 1 and 2. Each experiment is run for 10 trials, and the parameters for our IGNMF and B-IGNMF are set as follows: λ=0.01 and δ=0.01 for both databases and r=200 for the FERET database and r=68 for the CMU-PIE database. Then the average accuracies and the mean running time are recorded.Figure 1
All images of one person from FERET database.Figure 2
All images of one person from CMU-PIE database.


### 4.1. Incremental Study for Single Image

In these experiments, we choose5 images for each individual as the training set from the FERET database and 42 images for each individual from the CMU-PIE database. Our experiments are performed as follows: first, GNMF and NMF are chosen for initialization; second, IGNMF and INMF are performed to incremental study; GNMF and NMF are also performed by rerunning GNMF and NMF every time when new image comes. We choose one image of each individual from the rest of the database to incremental study, so all algorithms were run at a total of 200 times for the FERET database and 68 times for the CMU-PIE database. Notice INMF is an unsupervised learning algorithm, so unsupervised IGNMF is performed.Figures3 and 4 illustrate the curves of recognition rates for INMF, IGNMF, NMF, and GNMF during incremental study. We can see that when a small number of new images come, incremental methods (INMF and IGNMF) perform better than canonical methods (NMF and GNMF). We also observe that incremental methods can keep the recognition rate increasing smoothly with the number of images increasing; while canonical methods would make the recognition rate fluctuating. This is because every time when we rerun the canonical methods, the initial values for U and V are randomly assigned; different initial values would lead to different local minimum value, which in turn affect the recognition rate significantly. It is also noted that the recognition rates of IGNMF and GNMF are better than those of NMF and INMF; this is because the use of the manifold method, which preserves the geometrical information of the original data, contributes to the improvement of the recognition rate.Figure 3
The average recognition rate during incremental study for the FERET database.Figure 4
The average recognition rate during incremental study for the CMU-PIE database.Figures5 and 6 illustrate the running time of the selected algorithms in both databases, from the figure we can see that the mean running time of IGNMF for single image is close then INMF, while faster than GNMF and NMF, which means IGNMF achieved better recognition rate than INMF while faster than it.Figure 5
The mean running time during incremental study with single image for the FERET database.Figure 6
The mean running time during incremental study with single image for the CMU-PIE database.


### 4.2. Incremental Study for One Batch of Images Belonging to One Class

In this section, our B-IGNMF, and the other two typical incremental algorithms (CINMF and IOPNMF) are performed along with supervised GNMF, unsupervised GNMF, and NMF. Because CINMF is a supervised learning algorithm while IOPNMF is an unsupervised one, supervised B-IGNMF (BIGNMF-S) and unsupervised B-IGNMF (BIGNMF-U) are both performed.We choose5 images for each individual as the training set from the FERET database and 42 images for each individual from the CMU-PIE database. First, we choose 195 individuals from the FERET database and 63 individuals from the CMU-PIE database for study. Second, one of the rest of five individuals is chosen to add for incremental study, total 5 times. The parameters of CINMF are set to α=10, β=10-7, and r0=6 for the FERET database and α=0.1, β=10-4, and r0=6 for the CMU-PIE database; the parameters of IOPNMF are set to r=200 for the FERET database and r=136 for the CMU-PIE database. Tables 1 and 2 showed the recognition rates for two databases; “Add 1” means the recognition rate of adding one batch of images into “Start,” and “Add 2” means the recognition rate of adding another one batch of images into “Add 1,” and so on.Table 1
The recognition rates (%) for the FERET database during adding 5 batches of images belonging to one class.
Supervised methods
Unsupervised methods
BIGNMF-S
GNMF-S
CINMF
BIGNMF-U
GNMF-U
IOPNMF
NMF
Start
70.77
70.77
67.18
68.72
68.72
61.67
62.41
Add 1
70.28
69.47
66.84
68.37
65.5
61.52
61.12
Add 2
69.86
69.04
67.89
67.89
66.24
61.42
60.58
Add 3
69.44
70.54
67.3
67.3
67
61.4
61.89
Add 4
69.22
69.1
67.09
67
69
61.58
61.98
Add 5
70.28
69.47
66.84
68.37
65.5
61.52
61.12Table 2
The recognition rates (%) for the CMU-PIE database during adding 5 batches of images belonging to one class.
Supervised methods
Unsupervised methods
BIGNMF-S
GNMF-S
CINMF
BIGNMF-U
GNMF-U
IOPNMF
NMF
Start
85.05
85.05
82.36
83.64
83.64
50.34
79.20
Add 1
84.92
83.48
82.8
83.47
82.25
50.33
78.16
Add 2
84.79
83.77
82.66
83.3
83.02
50.66
78.54
Add 3
84.6
84.24
82.7
83.17
82.36
50.54
78.8
Add 4
84.62
84.5
82.8
83.13
82.46
50.75
78.88
Add 5
84.1
83.58
82.5
82.17
82.62
50.63
78.98Tables1 and 2 showed the recognition rates for two databases. We can see that the recognition rate of our BIGNMF is close to GNMF, both for the supervised one and the unsupervised one. In some cases BIGNMF is slightly better than GNMF. The recognition rates of GNMF-U, GNMF-S, and NMF are fluctuating during incremental study. In the experiments we found that CINMF was the fastest one to start (study without incremental); it needs less than 40 s for the FERET database and less than 15 s for CMU-PIE database, but during the incremental process, the recognition rate of our BIGNMF outperforms CINMF and is much more faster than CINMF. It is noted that the recognition rate of IOPNMF performs close to NMF for the FERET database while the worst is for the CMU-PIE database; the reason does not concern us.Figures7 and 8 illustrate the running time of the selected algorithms in both databases; from the figure we can see that the mean running time of BIGNMFs for one batch of images belonging to one class is faster than other NMF-based incremental algorithms, both for the supervised one and the unsupervised one, which means our proposed algorithms achieved better recognition rate than other NMF-based incremental algorithms, while faster than then.Figure 7
The mean running time during incremental study with images belonging to one class for the FERET database.Figure 8
The mean running time during incremental study with images belonging to one class for the CMU-PIE database.


### 4.3. Incremental Study for One Batch of Images Belonging to Different Classes

In this section, incremental study for one batch of images belonging to different classes is performed. Our B-IGNMF, both supervised method and unsupervised method, is selected, along with supervised GNMF, unsupervised GNMF, IOPNMF, and NMF.Experiments are designed as follows: we choose4 images for each individual (totally 7 images) as the starting training set from the FERET database; the rest of the images are considered as the testing set. For each incremental study, one image for each individual from the testing set is selected as one batch of images to incremental study, totally 200 images for each batch. The incremental study for FERET is performed twice. For the CMU-PIE database, we choose 42 images for each individual (totally 56 images) as the starting training set, then the rest of the images are considered as the testing set. For each incremental study, 2 images for each individual from the testing set are selected as one batch of images to incremental study, total 68×2 images for each batch. The incremental study for FERET is performed 5 times. Tables 3 and 4 showed the recognition rates for two databases; “Add 1” means the recognition rate of adding one batch of images into “Start,” and “Add 2” means the recognition rate of adding another one batch of images into “Add 1,” and so on.Table 3
The recognition rates (%) for the FERET database during adding 2 batches of images belonging to different classes.
Supervised methods
Unsupervised methods
BIGNMF-S
GNMF-S
BIGNMF-U
GNMF-U
IOPNMF
NMF
Start
58.53
58.53
57.24
57.24
49.54
55.06
Add 1
63.41
60.36
60.46
61.93
59.63
59.28
Add 2
69.14
70.94
69.08
71.43
67
67.75Table 4
The recognition rates (%) for the CMU-PIE database during adding 5 batches of images belonging to different classes.
Supervised methods
Unsupervised methods
BIGNMF-S
GNMF-S
BIGNMF-U
GNMF-U
IOPNMF
NMF
Start
81.37
81.37
79.15
79.64
46.32
79.01
Add 1
81.46
80.78
79.21
78.77
51.23
79.14
Add 2
81.26
81.98
81.29
81.75
54.85
79.85
Add 3
83.28
82.45
81.36
81.03
53.86
79.38
Add 4
83.3
83.45
83.61
83.59
51.96
80.28
Add 5
84.75
84.49
84.73
84.58
51.47
81.97Tables3 and 4 showed the recognition rates for two databases; we can see that the recognition rate of our BIGNMF, both the supervised one and the unsupervised one, is close to that of GNMF and better than that of NMF. Also, we can see that the recognition rate for both BIGNMFs is increasing while the new batch of images comes, which illustrate the effectiveness of the new incremental study algorithms. Note in the experment of the FERET database, in the starting, there are 4 images for each individual, totally 800 images; after adding the second batch of images, we added totally 400 images (2 images for each individual). Which means during the 50% amount of new images to incremental study, our BIGNMF still works. It is noted that the recognition rate of IOPNMF performs close to NMF for the FERET database while the worst for the CMU-PIE database; the reason is unknown.Figures9 and 10 illustrate the mean running times for all the selected algorithms in both database. From the figures we can see that the mean running time of our BIGNMFs for one batch of images belonging to different classes is faster than other NMF-based incremental algorithms, both for the supervised one and the unsupervised one, which means the recognition rate of our proposed algorithms is close to rerunning GNMF algorithms (sometimes slightly better), but faster.Figure 9
The mean running time during incremental study with images belonging to different classes for the FERET database.Figure 10
The mean running time during incremental study with images belonging to different classes for the CMU-PIE database.


## 4.1. Incremental Study for Single Image

In these experiments, we choose5 images for each individual as the training set from the FERET database and 42 images for each individual from the CMU-PIE database. Our experiments are performed as follows: first, GNMF and NMF are chosen for initialization; second, IGNMF and INMF are performed to incremental study; GNMF and NMF are also performed by rerunning GNMF and NMF every time when new image comes. We choose one image of each individual from the rest of the database to incremental study, so all algorithms were run at a total of 200 times for the FERET database and 68 times for the CMU-PIE database. Notice INMF is an unsupervised learning algorithm, so unsupervised IGNMF is performed.Figures3 and 4 illustrate the curves of recognition rates for INMF, IGNMF, NMF, and GNMF during incremental study. We can see that when a small number of new images come, incremental methods (INMF and IGNMF) perform better than canonical methods (NMF and GNMF). We also observe that incremental methods can keep the recognition rate increasing smoothly with the number of images increasing; while canonical methods would make the recognition rate fluctuating. This is because every time when we rerun the canonical methods, the initial values for U and V are randomly assigned; different initial values would lead to different local minimum value, which in turn affect the recognition rate significantly. It is also noted that the recognition rates of IGNMF and GNMF are better than those of NMF and INMF; this is because the use of the manifold method, which preserves the geometrical information of the original data, contributes to the improvement of the recognition rate.Figure 3
The average recognition rate during incremental study for the FERET database.Figure 4
The average recognition rate during incremental study for the CMU-PIE database.Figures5 and 6 illustrate the running time of the selected algorithms in both databases, from the figure we can see that the mean running time of IGNMF for single image is close then INMF, while faster than GNMF and NMF, which means IGNMF achieved better recognition rate than INMF while faster than it.Figure 5
The mean running time during incremental study with single image for the FERET database.Figure 6
The mean running time during incremental study with single image for the CMU-PIE database.


## 4.2. Incremental Study for One Batch of Images Belonging to One Class

In this section, our B-IGNMF, and the other two typical incremental algorithms (CINMF and IOPNMF) are performed along with supervised GNMF, unsupervised GNMF, and NMF. Because CINMF is a supervised learning algorithm while IOPNMF is an unsupervised one, supervised B-IGNMF (BIGNMF-S) and unsupervised B-IGNMF (BIGNMF-U) are both performed.We choose5 images for each individual as the training set from the FERET database and 42 images for each individual from the CMU-PIE database. First, we choose 195 individuals from the FERET database and 63 individuals from the CMU-PIE database for study. Second, one of the rest of five individuals is chosen to add for incremental study, total 5 times. The parameters of CINMF are set to α=10, β=10-7, and r0=6 for the FERET database and α=0.1, β=10-4, and r0=6 for the CMU-PIE database; the parameters of IOPNMF are set to r=200 for the FERET database and r=136 for the CMU-PIE database. Tables 1 and 2 showed the recognition rates for two databases; “Add 1” means the recognition rate of adding one batch of images into “Start,” and “Add 2” means the recognition rate of adding another one batch of images into “Add 1,” and so on.Table 1
The recognition rates (%) for the FERET database during adding 5 batches of images belonging to one class.
Supervised methods
Unsupervised methods
BIGNMF-S
GNMF-S
CINMF
BIGNMF-U
GNMF-U
IOPNMF
NMF
Start
70.77
70.77
67.18
68.72
68.72
61.67
62.41
Add 1
70.28
69.47
66.84
68.37
65.5
61.52
61.12
Add 2
69.86
69.04
67.89
67.89
66.24
61.42
60.58
Add 3
69.44
70.54
67.3
67.3
67
61.4
61.89
Add 4
69.22
69.1
67.09
67
69
61.58
61.98
Add 5
70.28
69.47
66.84
68.37
65.5
61.52
61.12Table 2
The recognition rates (%) for the CMU-PIE database during adding 5 batches of images belonging to one class.
Supervised methods
Unsupervised methods
BIGNMF-S
GNMF-S
CINMF
BIGNMF-U
GNMF-U
IOPNMF
NMF
Start
85.05
85.05
82.36
83.64
83.64
50.34
79.20
Add 1
84.92
83.48
82.8
83.47
82.25
50.33
78.16
Add 2
84.79
83.77
82.66
83.3
83.02
50.66
78.54
Add 3
84.6
84.24
82.7
83.17
82.36
50.54
78.8
Add 4
84.62
84.5
82.8
83.13
82.46
50.75
78.88
Add 5
84.1
83.58
82.5
82.17
82.62
50.63
78.98Tables1 and 2 showed the recognition rates for two databases. We can see that the recognition rate of our BIGNMF is close to GNMF, both for the supervised one and the unsupervised one. In some cases BIGNMF is slightly better than GNMF. The recognition rates of GNMF-U, GNMF-S, and NMF are fluctuating during incremental study. In the experiments we found that CINMF was the fastest one to start (study without incremental); it needs less than 40 s for the FERET database and less than 15 s for CMU-PIE database, but during the incremental process, the recognition rate of our BIGNMF outperforms CINMF and is much more faster than CINMF. It is noted that the recognition rate of IOPNMF performs close to NMF for the FERET database while the worst is for the CMU-PIE database; the reason does not concern us.Figures7 and 8 illustrate the running time of the selected algorithms in both databases; from the figure we can see that the mean running time of BIGNMFs for one batch of images belonging to one class is faster than other NMF-based incremental algorithms, both for the supervised one and the unsupervised one, which means our proposed algorithms achieved better recognition rate than other NMF-based incremental algorithms, while faster than then.Figure 7
The mean running time during incremental study with images belonging to one class for the FERET database.Figure 8
The mean running time during incremental study with images belonging to one class for the CMU-PIE database.


## 4.3. Incremental Study for One Batch of Images Belonging to Different Classes

In this section, incremental study for one batch of images belonging to different classes is performed. Our B-IGNMF, both supervised method and unsupervised method, is selected, along with supervised GNMF, unsupervised GNMF, IOPNMF, and NMF.Experiments are designed as follows: we choose4 images for each individual (totally 7 images) as the starting training set from the FERET database; the rest of the images are considered as the testing set. For each incremental study, one image for each individual from the testing set is selected as one batch of images to incremental study, totally 200 images for each batch. The incremental study for FERET is performed twice. For the CMU-PIE database, we choose 42 images for each individual (totally 56 images) as the starting training set, then the rest of the images are considered as the testing set. For each incremental study, 2 images for each individual from the testing set are selected as one batch of images to incremental study, total 68×2 images for each batch. The incremental study for FERET is performed 5 times. Tables 3 and 4 showed the recognition rates for two databases; “Add 1” means the recognition rate of adding one batch of images into “Start,” and “Add 2” means the recognition rate of adding another one batch of images into “Add 1,” and so on.Table 3
The recognition rates (%) for the FERET database during adding 2 batches of images belonging to different classes.
Supervised methods
Unsupervised methods
BIGNMF-S
GNMF-S
BIGNMF-U
GNMF-U
IOPNMF
NMF
Start
58.53
58.53
57.24
57.24
49.54
55.06
Add 1
63.41
60.36
60.46
61.93
59.63
59.28
Add 2
69.14
70.94
69.08
71.43
67
67.75Table 4
The recognition rates (%) for the CMU-PIE database during adding 5 batches of images belonging to different classes.
Supervised methods
Unsupervised methods
BIGNMF-S
GNMF-S
BIGNMF-U
GNMF-U
IOPNMF
NMF
Start
81.37
81.37
79.15
79.64
46.32
79.01
Add 1
81.46
80.78
79.21
78.77
51.23
79.14
Add 2
81.26
81.98
81.29
81.75
54.85
79.85
Add 3
83.28
82.45
81.36
81.03
53.86
79.38
Add 4
83.3
83.45
83.61
83.59
51.96
80.28
Add 5
84.75
84.49
84.73
84.58
51.47
81.97Tables3 and 4 showed the recognition rates for two databases; we can see that the recognition rate of our BIGNMF, both the supervised one and the unsupervised one, is close to that of GNMF and better than that of NMF. Also, we can see that the recognition rate for both BIGNMFs is increasing while the new batch of images comes, which illustrate the effectiveness of the new incremental study algorithms. Note in the experment of the FERET database, in the starting, there are 4 images for each individual, totally 800 images; after adding the second batch of images, we added totally 400 images (2 images for each individual). Which means during the 50% amount of new images to incremental study, our BIGNMF still works. It is noted that the recognition rate of IOPNMF performs close to NMF for the FERET database while the worst for the CMU-PIE database; the reason is unknown.Figures9 and 10 illustrate the mean running times for all the selected algorithms in both database. From the figures we can see that the mean running time of our BIGNMFs for one batch of images belonging to different classes is faster than other NMF-based incremental algorithms, both for the supervised one and the unsupervised one, which means the recognition rate of our proposed algorithms is close to rerunning GNMF algorithms (sometimes slightly better), but faster.Figure 9
The mean running time during incremental study with images belonging to different classes for the FERET database.Figure 10
The mean running time during incremental study with images belonging to different classes for the CMU-PIE database.


## 5. Conclusions

In this paper, a novel incremental study method named incremental graph regularized nonnegative matrix factorization (IGNMF) has been proposed for face recognition. IGNMF introduces the graph regularized nonnegative matrix factorization algorithm into incremental study. The proposed IGNMF is able to preserve discrimination information under incremental study framework. In addition, we adapted our IGNMF algorithm to deal with learning from image batches, resulting in another new learning method called Batch IGNMF (B-IGNMF). Experiments show that the recognition rates of our IGNMF and B-IGNMF algorithms are close to GNMF algorithms while they run faster than GNMF algorithms. The running times of our IGNMF and B-IGNMF algorithms are close to INMF, faster than other popular NMF-based face recognition incremental algorithms, while the recognition rate of our IGNMF and B-IGNMF algorithms outperforms them.Finally we point out the fact that if IGNMF and BIGNMF run too many times, the recognition rate would worsen than that of rerun GNMF. The reason for this is the assumption thatVk remains unchanged during the iterations and cannot hold if algorithms run too many times. So our future work will be focusing on how to resolve this issue.



---

*Source: 928051-2014-05-19.xml*