# Graph Regularized Nonnegative Matrix Factorization with Sparse Coding

Authors: Chuang Lin; Meng Pang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In this paper, we propose a sparseness constraint NMF method, named graph regularized matrix factorization with sparse coding (GRNMF_SC). By combining manifold learning and sparse coding techniques together, GRNMF_SC can efficiently extract the basic vectors from the data space, which preserves the intrinsic manifold structure and also the local features of original data. The target function of our method is easy to propose, while the solving procedures are really nontrivial; in the paper we gave the detailed derivation of solving the target function and also a strict proof of its convergence, which is a key contribution of the paper. Compared with sparseness constrained NMF and GNMF algorithms, GRNMF_SC can learn much sparser representation of the data and can also preserve the geometrical structure of the data, which endow it with powerful discriminating ability. Furthermore, the GRNMF_SC is generalized as supervised and unsupervised models to meet different demands. Experimental results demonstrate encouraging results of GRNMF_SC on image recognition and clustering when comparing with the other state-of-the-art NMF methods.


---

## Body

## 1. Introduction

Previous studies have shown that there is a psychological and physiological evidence for parts-based representation in the human brain [1–5]. NMF is such kind of parts-based matrix factorization methods, which can find out the local features from the original data in nonnegative sense. Indeed, the nonnegative constraint leads to a parts-based representation because it allows only additive combinations of components, not subtractive ones. Generally, NMF method is to find two nonnegative matrices whose product provides a good approximation to the original matrix, and, at the same time, it can also learn the parts of objects, which make them very important in some real applications, for example, in face recognition [6–9] and document clustering [10, 11] fields.However, the standard NMF [5, 6] algorithm has several limitations, which has been discussed extensively. One of the notable limitations of standard NMF is that it does not always result in completely parts-based representations. Researchers tried to solve this problem by incorporating sparseness constraints [12–14]. These approaches extended the NMF framework to include an adjustable sparseness parameter to learn more localized representation. However, previous sparseness constraint NMF approaches paid main attention to the sparseness property, while ignoring preserving the intrinsic geometric structure of the original data, which is vital for classification and clustering.Recent research shows that when the data is sampled from a probability distribution that resides in or nearby to a submanifold of the ambient space,manifold learning [15–19] can be used to preserve the intrinsic (geometrical) structure. In order to preserve the intrinsic structure of the original data, He and Cai proposed Graph Regularized NMF (GNMF) methods [20, 21], which incorporated local preserving projection (LPP) technique [22] to NMF framework.The experimental results showed that GNMF achieved higher recognition rates and better clustering effect in some popular facial databases (e.g., ORL and YALE database) comparing with previous sparseness constraint NMF [20, 21]. It means for some datasets, which have apparent geometrical structure, that GNMF really works. While, GNMF still has disadvantage, it cannot ensure the sparseness of the factorization results, which limited the discriminative ability and also increased the computational expense and memory space. Hence, we are motivated to combine the advantage of manifold and sparseness constraint and propose the GRNMF_SC algorithm, which can not only preserve the geometrical structure, but also learn much sparser representations of the input data.It needs to emphasize that it is nontrivial to solve the objective function which simultaneously incorporates the Laplacian regularization and sparseness constraint into the NMF framework, because the sophisticated L1-norm solving tools cannot be adopted directly. We start from the initial idea of designing GNMF and incorporate the sparseness constraint smoothly. The concrete steps are first, construct a convex objection function by imposing the above constrains and then develop an optimization algorithm with multiplicative update rules to minimize this objective function. Finally, prove the algorithm can converge to a local minimum. Furthermore, we extend GRNMF_SC to both supervised (S-GRNMF_SC) and unsupervised versions (GRNMF_SC) for image recognition and clustering, respectively; in clustering, the class labels are not available. Experimental results demonstrate that supervised GRNMF_SC achieved higher recognition rates, especially in occluded face recognition, when comparing with the typical sparseness based NMF and manifold based NMF methods, and the unsupervised GRNMF_SC obtained better clustering performance comparing with the popular clustering algorithms.The rest of the paper is organized as follows. In Section2, a brief review of standard NMF and its typical sparse variants is given. In Section 3, the proposed GRNMF_SC method and a proof of its convergence are given. Experimental results on image recognition and clustering are presented in Section 4. We conclude the paper and plan the future work in Section 5.


## 2. Reviews of Standard NMF and Its Sparse Variants

In this section, we briefly describe the standard NMF algorithm [5] and two typical sparseness constraint NMF algorithms [8, 13]; the reason of introducing the two sparseness constraint NMF algorithms is that our method is inspired by them. The introduction of GNMF is merged with GRNMF_SC in Section 3.


### 2.1. Nonnegative Matrix Factorization (NMF)

First, standard NMF [5, 6] is introduced. Given a data matrix X=[x1,…,xn]∈Rm×n, each column of X is an m-dimensionalsample vector with nonnegative values. NMF aims to find two nonnegative matrices U∈Rm×r and V∈Rm×r whose product can well approximate the original matrix. That is, it is to minimize the following cost function:(1)O=X-UVTF2.F represents the Frobenius norm. Since the objective function is not convex inU andV together, we are not expected to find the global minimum of O. Lee and Seung [5] presented the following iterative update rule:(2)uij⟸uijXVijUVTVij,vij⟸vijXTUijVUTUij.It was proven that the above two equations will find local minima of the objective function O.


### 2.2. Local Nonnegative Matrix Factorization (LNMF)

Inspired by the original NMF algorithm [5], Li et al. [8] introduced the local nonnegative matrix factorization (LNMF) algorithm which is intended for learning spatially localized, parts-based representation of visual patterns. The aim of their work was to obtain truly localized, parts-based components by imposing three additional constraints on classical NMF.Taking the factorization problem defined in (1), let B=[bi,j]=UTU and H=[hi,j]=VVT, where B,H∈Rr×r. LNMF is aimed at learning local features by imposing the following three additional constraints on the NMF basis:(1)
Maximum orthogonality ofU. This constraint imposes that different bases should be as orthogonal as possible so to minimize redundancy between different bases. This can be imposed by ∑i≠jbij=min⁡.(2)
Maximum expressiveness ofU. This constraint reveals that only components giving most important information should be retained. This is imposed by ∑ihii=∑ivij2=max⁡.(3)
Maximum sparseness in encoding matrixV. It should contain as many zero elements as possible in coefficient matrix V. In other words, the number of basis components required to represent data matrix X is minimized. This can be imposed by ∑ibii=∑iuij2=min⁡, where uj=[uij]i=1m is a basis vector.The incorporation of the above constraints leads to the following constrained divergence as the objective function for LNMF:(3)DX∥UV=∑i,jXijlog⁡XijUVij-Xij+UVij+α∑i,jbij-β∑i,jhij,where α,β>0 are some constants. The solution to the above constrained minimization can be presented following multiplicative updating rules:(4)vij⟸Vij∑kUkiXkj∑lUklVlj,uij⟸Uij∑k(VjkXik)/∑lUliVjk∑kVjk,uij⟸Uij∑kUkj.


### 2.3. Sparse Nonnegative Matrix Factorization (SNMF)

Similar to the LNMF algorithm, Liu et al. [13] incorporated linear sparse coding to NMF. The core idea of SNMF is adding sparseness constraints to encoding matrix when conducting matrix factorization. SNMF could learn parts-based representation via fully multiplicative updates because of it adapting a generalized Kullback-Leibler divergence instead of mean square error for approximation error. Thus, the sparse NMF functional is (5)DX∥UV=∑i,jXijlog⁡XijUVij-Xij+UVij+α∑i,jVij,where α≥0.SNMF ensured sparseness via minimizing the sum of allVij. The multiplicative update rules for matrix U,V are(6)vij⟸Vij∑k(UkiXkj)/∑lUklVlj1+α,uij⟸Uij∑k(VjkXik)/∑lUliVjk∑kVjk,uij⟸Uij∑kUkj.


## 2.1. Nonnegative Matrix Factorization (NMF)

First, standard NMF [5, 6] is introduced. Given a data matrix X=[x1,…,xn]∈Rm×n, each column of X is an m-dimensionalsample vector with nonnegative values. NMF aims to find two nonnegative matrices U∈Rm×r and V∈Rm×r whose product can well approximate the original matrix. That is, it is to minimize the following cost function:(1)O=X-UVTF2.F represents the Frobenius norm. Since the objective function is not convex inU andV together, we are not expected to find the global minimum of O. Lee and Seung [5] presented the following iterative update rule:(2)uij⟸uijXVijUVTVij,vij⟸vijXTUijVUTUij.It was proven that the above two equations will find local minima of the objective function O.


## 2.2. Local Nonnegative Matrix Factorization (LNMF)

Inspired by the original NMF algorithm [5], Li et al. [8] introduced the local nonnegative matrix factorization (LNMF) algorithm which is intended for learning spatially localized, parts-based representation of visual patterns. The aim of their work was to obtain truly localized, parts-based components by imposing three additional constraints on classical NMF.Taking the factorization problem defined in (1), let B=[bi,j]=UTU and H=[hi,j]=VVT, where B,H∈Rr×r. LNMF is aimed at learning local features by imposing the following three additional constraints on the NMF basis:(1)
Maximum orthogonality ofU. This constraint imposes that different bases should be as orthogonal as possible so to minimize redundancy between different bases. This can be imposed by ∑i≠jbij=min⁡.(2)
Maximum expressiveness ofU. This constraint reveals that only components giving most important information should be retained. This is imposed by ∑ihii=∑ivij2=max⁡.(3)
Maximum sparseness in encoding matrixV. It should contain as many zero elements as possible in coefficient matrix V. In other words, the number of basis components required to represent data matrix X is minimized. This can be imposed by ∑ibii=∑iuij2=min⁡, where uj=[uij]i=1m is a basis vector.The incorporation of the above constraints leads to the following constrained divergence as the objective function for LNMF:(3)DX∥UV=∑i,jXijlog⁡XijUVij-Xij+UVij+α∑i,jbij-β∑i,jhij,where α,β>0 are some constants. The solution to the above constrained minimization can be presented following multiplicative updating rules:(4)vij⟸Vij∑kUkiXkj∑lUklVlj,uij⟸Uij∑k(VjkXik)/∑lUliVjk∑kVjk,uij⟸Uij∑kUkj.


## 2.3. Sparse Nonnegative Matrix Factorization (SNMF)

Similar to the LNMF algorithm, Liu et al. [13] incorporated linear sparse coding to NMF. The core idea of SNMF is adding sparseness constraints to encoding matrix when conducting matrix factorization. SNMF could learn parts-based representation via fully multiplicative updates because of it adapting a generalized Kullback-Leibler divergence instead of mean square error for approximation error. Thus, the sparse NMF functional is (5)DX∥UV=∑i,jXijlog⁡XijUVij-Xij+UVij+α∑i,jVij,where α≥0.SNMF ensured sparseness via minimizing the sum of allVij. The multiplicative update rules for matrix U,V are(6)vij⟸Vij∑k(UkiXkj)/∑lUklVlj1+α,uij⟸Uij∑k(VjkXik)/∑lUliVjk∑kVjk,uij⟸Uij∑kUkj.


## 3. Graph Regularized Nonnegative Matrix Factorization with Sparse Coding (GRNMF_SC)

As mentioned earlier, He and Cai [20, 21] proposed a GNMF algorithm. By utilizing the Laplacian regularization to NMF, GNMF can preserve the intrinsic structure of the data efficiently. GNMF can have more strong discriminative power than the classic NMF, when the dataset has apparent geometrical structure. However, since GNMF did not impose any sparse constraint to the basis matrix U or encoding matrix V, it cannot learn the sparse enough representation. In this part, we incorporate sparse coding into GNMF and propose a GRNMF_SC algorithm.


### 3.1. Graph Regularized Nonnegative Matrix Factorization (GNMF)

GNMF first constructs an affinity graph to encode the geometrical information and then seeks a nonnegative matrix factorization which respects the graph structure. The procedure can be stated as follows.Step 1.
Consider a graph withn vertices where each vertex corresponds to a data point. The edge weight matrix W is defined as follows:(7)Wij=1,ifxi∈Npxjorxj∈Npxi,0,otherwise,where Np(xi) denotes the set of p nearest neighbors of xi. Define L=D-W, where D is a diagonal matrix whose unit entries are column sums of W, Dii=∑jWij.Step 2.
Letfk(xi)=vik be the function that maps the original data point xi onto the axis uk. GNMF then uses fkM2 to measure the smoothness of the function fk along the geodesics in the intrinsic geometry of the data. When we consider the case that the data is a compact submanifold M∈Rm, then the discrete approximation of fkM2 is computed as follows:(8)fkM2=12∑i,j=1nfkxi-fkxj2Wij=vkTLvk.By minimizing fkM2, we get a mapping function fk which is sufficiently smooth on the data manifold. An intuitive explanation of minimizing fkM2 is that if two data points xi and xj are close, then fk(xi) and fk(xj) are similar to each other.Step 3.
Finally, GNMF incorporates the constraint and minimizes the new objective function(9)O=X-UVTF2+λTr⁡VTLV,with the constraint that uij and vij are nonnegative. Tr⁡(·) denotes the trace of a matrix, and λ≥0 is a regularization parameter.


### 3.2. GRNMF_SC

In order to improve the degree of sparseness of coefficient matrix (VT) and preserve the intrinsic structure of the high dimensional data, we add an L1-norm regularization to the coefficient matrix. By this way, we expect that each sample in X can be represented by a linear combination of only few basis vectors in U, and thus the sparseness can be guaranteed. The new objective function is as follows:(10)O=X-UVTF2+λTr⁡(VTLV)+α∑i=1nvi1s.tU,V≥0,uj=1,∀j,where L=D-W and Dii=∑jWij. For S-GRNMF_SC, we set Wij=1, if xi∈Np(xj) or xj∈Np(xi) and ci=cj, and Wij=0 otherwise. ci and cj denote the class labels of xi and xj. For unsupervised GRNMF_SC, the definition of Wij is the same as GNMF’s in Section 3.1. Finally, the multiplicative updating rules for the above objective function can be represented as(11)vij⟸vij2XTU+λWVij-α2VUTU+λDVij,uij⟸uijXVijUVTVij,uij⟸uij∑iuij.GRNMF_SC has fully multiplicative update rules with two parameters. When settingλ=0, then GRNMF_SC reduces to NNSC [12]. When setting α=0, GRNMF_SC reduces to GNMF. Also, we find that the updating rules of encoding Matrix V could be rewritten as the following gradient decent format:(12)vij(t+1)=vij(t)+η∂O∂vij,η=Vij2VUTU+λDVij.In order to preserve the nonnegative property of coefficient matrix V, we should control the parameter α and λ to make η positive as well as small. The proof of our optimization scheme of GRNMF_SC is given next.The core idea of the proof is using auxiliary function technique as the EM algorithm and then taking turns updating basis matrixU and coefficient matrix V. We begin with the definition of the auxiliary function G(v,vt).Definition 1.
G
(
v
,
v
t
) is an auxiliary function for F(v) if the following conditions are satisfied:(13)Gv,vt≥Fv,Gv,v=Fv.
The reason why the auxiliary function is vital for proving is owing to the following theorem.Theorem 2.
IfG is an auxiliary function of F, then F is nonincreasing under the update(14)vt+1=argmin⁡vGv,vt.Proof.
F
(
v
t
+
1
)
≤
G
(
v
t
,
v
t
+
1
)
≤
G
(
v
t
,
v
t
)
=
F
(
v
t
).
We start first to derive the multiplicative update steps of encoding matrixV. The objective function of GRNMF_SC can be rewritten as(15)O=∑i=1m∑j=1nxij-∑l=1kuilvjl2+λ∑l=1k∑i=1n∑j=1nvjlLjivil+α∑l=1k∑j=1nvlj.
Considering any elementvij in V, we use Fij′ and Fij′′ to denote the first-order derivative and second-order derivative of the objective function O:(16)Fij′=∂O∂Vij=-2XTU+2VUTU+2λLVij+αFij′′=2UTUjj+2λLii.
And then, we define the auxiliary function as(17)Gv,vijt=Fijvijt+Fij′vijtv-vijt+VUTUij+λDVijvijtv-vijt2.
We need to proveG(v,v)=F(v) and G(v,vij(t))≥Fij(v).
It is easy to proveG(v,v)=F(v). Next, to prove G(v,vij(t))>Fij(v), we derive the Taylor series expansion of Fij(v):(18)Fijv≈Fijvijt+Fij′vijtv-vijt+UTUjj+λLiiv-vijt2.The above holds because (19)VUTUij=∑l=1kvil(t)UTUlj≥vij(t)UTUjj,λDVij=λ∑l=1nDilvlj(t)≥λDiivij(t)≥λD-Hiivijt=λLiivijt.Finally we obtain (20)VUTUij+λDVijvij(t)≥UTUjj+λLii.In other words, G(v,vij(t))≥Fij(v).
According to Theorem2, by taking derivative with respect to vij(t)on (17) and setting the derived result to zero, the updating rule of V can be expressed as(21)vij⟸vij2XTU+λWVij-α2VUTU+λDVij.Similarly, we can also obtain the updating rule of U with regularization:(22)uij⟸uijXVijUVTVij,uij⟸uij∑iuij.


## 3.1. Graph Regularized Nonnegative Matrix Factorization (GNMF)

GNMF first constructs an affinity graph to encode the geometrical information and then seeks a nonnegative matrix factorization which respects the graph structure. The procedure can be stated as follows.Step 1.
Consider a graph withn vertices where each vertex corresponds to a data point. The edge weight matrix W is defined as follows:(7)Wij=1,ifxi∈Npxjorxj∈Npxi,0,otherwise,where Np(xi) denotes the set of p nearest neighbors of xi. Define L=D-W, where D is a diagonal matrix whose unit entries are column sums of W, Dii=∑jWij.Step 2.
Letfk(xi)=vik be the function that maps the original data point xi onto the axis uk. GNMF then uses fkM2 to measure the smoothness of the function fk along the geodesics in the intrinsic geometry of the data. When we consider the case that the data is a compact submanifold M∈Rm, then the discrete approximation of fkM2 is computed as follows:(8)fkM2=12∑i,j=1nfkxi-fkxj2Wij=vkTLvk.By minimizing fkM2, we get a mapping function fk which is sufficiently smooth on the data manifold. An intuitive explanation of minimizing fkM2 is that if two data points xi and xj are close, then fk(xi) and fk(xj) are similar to each other.Step 3.
Finally, GNMF incorporates the constraint and minimizes the new objective function(9)O=X-UVTF2+λTr⁡VTLV,with the constraint that uij and vij are nonnegative. Tr⁡(·) denotes the trace of a matrix, and λ≥0 is a regularization parameter.


## 3.2. GRNMF_SC

In order to improve the degree of sparseness of coefficient matrix (VT) and preserve the intrinsic structure of the high dimensional data, we add an L1-norm regularization to the coefficient matrix. By this way, we expect that each sample in X can be represented by a linear combination of only few basis vectors in U, and thus the sparseness can be guaranteed. The new objective function is as follows:(10)O=X-UVTF2+λTr⁡(VTLV)+α∑i=1nvi1s.tU,V≥0,uj=1,∀j,where L=D-W and Dii=∑jWij. For S-GRNMF_SC, we set Wij=1, if xi∈Np(xj) or xj∈Np(xi) and ci=cj, and Wij=0 otherwise. ci and cj denote the class labels of xi and xj. For unsupervised GRNMF_SC, the definition of Wij is the same as GNMF’s in Section 3.1. Finally, the multiplicative updating rules for the above objective function can be represented as(11)vij⟸vij2XTU+λWVij-α2VUTU+λDVij,uij⟸uijXVijUVTVij,uij⟸uij∑iuij.GRNMF_SC has fully multiplicative update rules with two parameters. When settingλ=0, then GRNMF_SC reduces to NNSC [12]. When setting α=0, GRNMF_SC reduces to GNMF. Also, we find that the updating rules of encoding Matrix V could be rewritten as the following gradient decent format:(12)vij(t+1)=vij(t)+η∂O∂vij,η=Vij2VUTU+λDVij.In order to preserve the nonnegative property of coefficient matrix V, we should control the parameter α and λ to make η positive as well as small. The proof of our optimization scheme of GRNMF_SC is given next.The core idea of the proof is using auxiliary function technique as the EM algorithm and then taking turns updating basis matrixU and coefficient matrix V. We begin with the definition of the auxiliary function G(v,vt).Definition 1.
G
(
v
,
v
t
) is an auxiliary function for F(v) if the following conditions are satisfied:(13)Gv,vt≥Fv,Gv,v=Fv.
The reason why the auxiliary function is vital for proving is owing to the following theorem.Theorem 2.
IfG is an auxiliary function of F, then F is nonincreasing under the update(14)vt+1=argmin⁡vGv,vt.Proof.
F
(
v
t
+
1
)
≤
G
(
v
t
,
v
t
+
1
)
≤
G
(
v
t
,
v
t
)
=
F
(
v
t
).
We start first to derive the multiplicative update steps of encoding matrixV. The objective function of GRNMF_SC can be rewritten as(15)O=∑i=1m∑j=1nxij-∑l=1kuilvjl2+λ∑l=1k∑i=1n∑j=1nvjlLjivil+α∑l=1k∑j=1nvlj.
Considering any elementvij in V, we use Fij′ and Fij′′ to denote the first-order derivative and second-order derivative of the objective function O:(16)Fij′=∂O∂Vij=-2XTU+2VUTU+2λLVij+αFij′′=2UTUjj+2λLii.
And then, we define the auxiliary function as(17)Gv,vijt=Fijvijt+Fij′vijtv-vijt+VUTUij+λDVijvijtv-vijt2.
We need to proveG(v,v)=F(v) and G(v,vij(t))≥Fij(v).
It is easy to proveG(v,v)=F(v). Next, to prove G(v,vij(t))>Fij(v), we derive the Taylor series expansion of Fij(v):(18)Fijv≈Fijvijt+Fij′vijtv-vijt+UTUjj+λLiiv-vijt2.The above holds because (19)VUTUij=∑l=1kvil(t)UTUlj≥vij(t)UTUjj,λDVij=λ∑l=1nDilvlj(t)≥λDiivij(t)≥λD-Hiivijt=λLiivijt.Finally we obtain (20)VUTUij+λDVijvij(t)≥UTUjj+λLii.In other words, G(v,vij(t))≥Fij(v).
According to Theorem2, by taking derivative with respect to vij(t)on (17) and setting the derived result to zero, the updating rule of V can be expressed as(21)vij⟸vij2XTU+λWVij-α2VUTU+λDVij.Similarly, we can also obtain the updating rule of U with regularization:(22)uij⟸uijXVijUVTVij,uij⟸uij∑iuij.


## 4. Experimental Results

The face recognition experiments were performed on two benchmarks, the ORL 48 × 48 database and YALE 32 × 32 database, to test the recognition rates of the proposed S-GRNMF_SC algorithm. The ORL contains 400 images, 10 different images per person for 40 individuals. For some individuals, the images were taken at different times. There are variations in facial expressions (open or closed eyes and smiling or nonsmiling) and facial details (glasses or no glasses). YALE database is more challenging than ORL, which contains 165 gray-scale images of 15 individuals. The images demonstrate variations in lighting condition (left-light, center-light, and right-light), facial expression (normal, happy, sad, sleepy, and surprised), and facial details (glasses or no glasses). The algorithms, NMF [5], LNMF [8], SNMF [13], GNMF [21], and FMD-NMF [23], are used for comparison. LNMF and SNMF are two classical sparseness based NMF; GNMF and FMD-NMF are two manifold based NMF; they are the ideal comparative targets to S-GRNMF_SC which merged the two kinds of merit. For all face recognition experiments, the nearest neighbor (NN) classifier was used, and the distance is measured by Euclidean metric.The clustering experiment was performed on COIL20 image. COIL20 database contains gray scale images of 20 objects viewed from varying angles and each object has 72 images. Four popular clustering algorithms,K-means, NMF [5], SNMF [13], and GNMF [21], were used as comparing algorithms. After the matrix factorization, we have a lower dimensional representation of each image. The clustering is then performed in this lower dimensional space. K-means is considered as a baseline method which simply performs clustering in the original feature space.


### 4.1. Recognition Results on ORL and YALE Database

In this part, the face recognition experiment is carried out on the ORL and YALE database. First, to evaluate all methods’ ability to dealing with differentGms for ORL database, a random subset with Gm(G3,G4,G5,G6,G7) is taken with labels to form the training set, respectively, and the corresponding remaining part Pn(P7,P6,P5,P4,P3) with labels is taken to form the testing set. For YALE database, Gm(G4,G5,G6,G7,G8) is taken to form the training set and the corresponding remaining part Pn(P7,P6,P5,P4,P3) is taken to form the testing set. For each given Gm/Pn, we averaged the results over 10 random splits. Tables 1 and 2 show the optimal average recognition rates obtained by NMF, LNMF, SNMF, GNMF, FMD-NMF, and S-GRNMF_SC with the same feature dimension in differentGms over 10 random splits.Table 1
Optimal average recognition rates ±  σ2 on ORL database with different number of training samples of each person (dimensions = 50).
Method
G
3
/
P
7
G
4
/
P
6
G
5
/
P
5
G
6
/
P
4
G
7
/
P
3
NMF
72.8% ± 2.0%
78.8% ± 1.5%
82.6% ± 2.0%
85.0% ± 3.5%
88.0% ± 3.5%
LNMF
61.4% ± 8.0%
65.4% ± 6.0%
67.5% ± 4.0%
71.3% ± 3.9%
74.2% ± 4.0%
SNMF
73.6% ± 1.0%
79.3% ± 1.0%
82.8% ± 2.0%
85.3% ± 2.0%
89.0% ± 1.5%
GNMF
73.9% ± 1.0%
80.9% ± 1.0%
83.8% ± 2.0%
86.2% ± 1.0%
89.5% ± 1.0%
FMD-NMF
72.5% ± 1.0%
82.1% ± 2.0%
87.0% ± 1.0%
88.5% ± 1.5%
92.0% ± 2.0%
S-GRNMF_SC
73.2% ± 2.0%
83.3% ± 3.0%
89.0% ± 2.0%
90.4% ± 1.0%
92.5% ± 2.0%Table 2
Optimal average recognition rates ±  σ2 on YALE database with different number of training samples of each person (dimensions = 50).
Method
G
4
/
P
7
G
5
/
P
6
G
6
/
P
5
G
7
/
P
4
G
8
/
P
3
NMF
62.8% ± 5.7%
64.4% ± 3.5%
67.7% ± 4.0%
76.3% ± 1.0%
80.8% ± 2.0%
LNMF
61.5% ± 1.0%
68.9% ± 1.0%
70.7% ± 1.5%
79.0% ± 2.0%
83.1% ±  2.0%
SNMF
63.6% ± 3.5%
65.3% ± 2.5%
70.0% ± 2.0%
77.7% ± 2.0%
82.2% ±  2.0%
GNMF
63.8% ± 2.9%
66.7% ± 2.0%
72.0% ± 2.0%
80.0% ± 1.5%
83.1% ±  2.0%
FMD-NMF
65.3% ± 2.0%
68.5% ± 1.8%
71.7% ± 3.0%
79.8% ± 3.0%
82.2% ± 3.0%
S-GRNMF_SC
67.0% ± 1.5%
70.2% ± 3.0%
73.3% ± 2.0%
83.3% ± 1.5%
85.4% ±  2.0%Figure1 shows the average recognition rates versus feature dimensions of all the competing algorithms. Note that the optimal average recognition rates are obtained over the whole feature dimensions. The feature dimension is chosen from 0 to 100 with intervals of 10 with different G5/P5s for ORL database and G7/P4 for YALE database.Figure 1
Average recognition rate of NMF, LNMF, SNMF, GNMF, and S-GRNMF_SC versus different feature dimensions on ORL and YALE databases.
(a)
ORL database (48 × 48)
(b)
YALE database (32 × 32)From Tables1 and 2 and Figure 1, it is shown that S-GRNMF_SC algorithm increases about 2% in average recognition rates compared with FMD-NMF algorithm and delivers nearly 4% of improvement recognition rates compared to GNMF and SNMF. In addition, FMD-NMF obtains the next best results, for the reason that FMD-NMF also utilizes the class label information and preserves the manifold structure like S-GRNMF_SC. GNMF and SNMF methods perform comparatively close to FMD-NMF. NMF is slightly worse than SNMF, while LNMF algorithm performs the worst; the reason is LNMF pays main attention to keep the bases orthogonal while ignoring the performance of coefficients; this leads to poor classification performance.


### 4.2. Learning Basis Images from the ORL and YALE Database

In this subsection, we use NMF, LNMF, GNMF, FMD-NMF, and the proposed S-GRNMF_SC algorithms to learn 25 and 49 basis images from the ORL and YALE database, respectively. Then we use the sparseness metric (SP) [24] to measure the sparseness of basis matrix as well as coefficients matrix. The sparseness measure, which is based on the relationship between the L1 norm and the L2 norm, is formularized as(23)SP(H)=N-∑hi/∑hi2N-1,where hi is a column vector of matrix H. If all elements of hi are equal, SP(H) is equal to zero; if hi only contains a single nonzero element, SP(H) is equal to unity. The basis images are shown in Figure 2. The sparseness of basis matrix and coefficient matrix is shown in Tables 3 and 4.Table 3
Sparseness comparison for different NMF models under different levels (r=25, r=49) on ORL database.
Method
Average sparseness on
Average sparseness on
Average sparseness on
Average sparseness on
U (r=25)
V
T (r=25)
U (r=49)
V
T (r=49)
NMF
0.262122
0.295615
0.311064
0.335885
LNMF
0.633281
0.006225
0.705528
0.007179
GNMF
0.264691
0.231159
0.318175
0.305258
FMD-NMF
0.433127
0.220854
0.505354
0.289466
S-GRNMF_SC
0.383589
0.312841
0.468214
0.364870Table 4
Sparseness comparison for different NMF models under different levels (r=25, r=49) on YALE database.
Method
Average sparseness on
Average sparseness on
Average sparseness on
Average sparseness on
U (r=25)
V
T (r=25)
U (r=49)
V
T (r=49)
NMF
0.412778
0.389463
0.469252
0.401235
LNMF
0.703995
0.025648
0.774678
0.027278
GNMF
0.457980
0.396353
0.536095
0.413464
FMD-NMF
0.512505
0.373300
0.605472
0.380108
S-GRNMF_SC
0.607605
0.428920
0.689776
0.446257Figure 2
5 × 5 and 7 × 7 basis images of NMF, LNMF, GNMF, FMD-NMF, and S-GRNMF_SC on ORL and YALE database.
(a)
5 × 5 and 7 × 7 basis images of NMF on ORL and YALE database
(b)
5 × 5 and 7 × 7 basis images of LNMF on ORL and YALE database
(c)
5 × 5 and 7 × 7 basis images of GNMF on ORL and YALE database
(d)
5 × 5 and 7 × 7 basis images of FMD-NMF on ORL and YALE database
(e)
5 × 5 and 7 × 7 basis images of S-GRNMF_SC on ORL and YALE databaseFrom the results, it is clear that the bases obtained by NMF and GNMF are additive, but not spatially localized for facial representations. In contrast, S-GRNMF_SC and FMD-NMF have the following advantages and improvements when compared with them. The bases learnt by S-GRNMF_SC and FMD-NMF are better than NMF and GNMF, since these bases not only reveal the additive property but also capture the discriminant information and preserve the manifold structure. In addition, though LNMF can obtain the spatially localized bases, it does not take the intrinsic structures of the data into account, which is also important in the classification task.


### 4.3. Face Reconstruction on the ORL Database

In this subsection, the reconstruction experiments of NMF, LNMF, GNMF, FMD-NMF, and S-GRNMF_SC algorithms are performed on the ORL database. We selected 4 different types, that is, men’s frontal view with no facial expression (MFV_NFE), men’s frontal view with wearing glasses (MFV_WG), men’s lateral view with smiling facial expression (MLV_SFE), and women’s frontal view with no facial expression (WFV_NFE), from images in the ORL database. The reconstructed images using these algorithms compared with the original ones are presented in Figure3, where the leftmost are the original images, and the images to the right are reconstructed images obtained by NMF, LNMF, GNMF, GRNMF_SC, and FMD-NMF, respectively. It is evident that the reconstruction quality of GRNMF_SC is better than the others’. This observation is validated by computing all methods’ reconstruction residual error through pixel gray value difference between the original and reconstructed images. The residual error is represented by the norm F2 of the residual matrix. The results are shown in Table 5. The reconstruction residual error of GRNMF_SC is the smallest in all cases except the first type. From these results, it is clear that the reconstruction quality by GRNMF_SC is robust to gender and different facial expressions. GNMF and FMD-NMF are next to GRNMF_SC. LNMF scheme performs the worst though it provides smoother reconstructions than other methods.Table 5
Reconstruction residual error of NMF, LNMF, GNMF, FMD-NMF, and GRNMF_SC with 4 kinds of selected images on the ORL.
Method
MFV_NFE
MLV_SFE
MFV_WG
WFV_NFE
NMF
17.09
14.23
40.47
35.29
LNMF
67.91
32.24
44.70
50.33
GNMF
26.53
15.46
31.08
23.42
S-GRNMF_SC
22.65
11.59
25.74
17.36
FMD-NMF
19.34
14.10
38.49
24.77Figure 3
Reconstruction effects by NMF, SNMF, LNMF, GNMF, S-GRNMF_SC, and FMD-NMF. From top to the bottom are MFV_NFE, MFV_WG, MLV_SFE, and WFV_NFE images. Leftmost are the original face images and from second to the last columns are reconstruction effects.
(a)
(b)
(c)
(d)


### 4.4. Occluded Face Recognition on ORL Database

NMF and its variants are parts-based representation algorithms; they can achieve better recognition results than other traditional appearance-based methods (e.g., LPP and LSDA) in the occluded face database. S-GRNMF_SC performs better than other traditional NMF algorithms. In order to highlight the superior advantage of S-GRNMF_SC against other NMF algorithms in the occluded face database, we give the experimental results in what follows. The size of sheltering patch is from 10 × 10, 15 × 15, 20 × 20, and 25 × 25 pixels, respectively, and the position is randomly selected. Figure4 shows the occluded face images.Figure 4
Occluded face samples: the sheltering patch is randomly placed on the faces, and the size is (from left to right) 10 × 10, 15 × 15, 20 × 20, and 25 × 25 pixels, respectively.
(a)
(b)
(c)
(d)Figure5 shows the recognition accuracies versus different feature dimensions with occluding patch size of 10 × 10, 15 × 15, 20 × 20, and 25 × 25 pixels on the ORL database, respectively. Table 6 presents optimal average recognition rates on occluded ORL database with different size of sheltering patch. From Figure 5 and Table 6, we can see that S-GRNMF_SC performs much better than other algorithms; there is about 5% to 20% improvement. The significant improvements are owing to the sparseness and manifold constraints in S-GRNMF_SC. Specifically, S-GRNMF_SC can obtain sparser representation than FMD-NMF; furthermore S-GRNMF_SC maintains more local information than GNMF, and more discriminant and geometrical information than standard NMF, LNMF, and SNMF. The occluding experiment strongly supports the necessity of imposing sparseness and manifold constraint simultaneously.Table 6
Optimal average recognition rates ±  σ2 on occluded ORL database with different size of sheltering patch (dimensions = 50).
Method
10
×
10
1
5
×
1
5
2
0
×
2
0
25
×
25
NMF
80.5% ± 2.0%
74.7% ± 1.5%
69.5% ± 2.0%
62.3% ± 1.0%
LNMF
59.5% ± 5.0%
55.7% ± 4.0%
51.7% ± 4.0%
45.6% ± 3.0%
SNMF
81.8% ± 1.5%
78.2% ± 2.0%
72.5% ± 2.0%
66.3% ± 2.0%
GNMF
82.5% ± 1.0%
79.3% ± 2.0%
73.3% ± 2.0%
68.0% ± 2.0%
FMD-NMF
83.2% ± 2.0%
80.5% ± 2.5%
74.0% ± 1.5%
68.5% ± 2.0%
S-GRNMF_SC
85.5% ± 1.0%
83.5% ± 2.0%
77.5% ± 2.0%
73.2% ± 2.0%Figure 5
Recognition accuracies versus different feature dimensions on ORL database with different occluding patch size.
(a)
Occluding patch size 10 × 10
(b)
Occluding patch size 15 × 15
(c)
Occluding patch size 20 × 20
(d)
Occluding patch size 25 × 25


### 4.5. Clustering Experiment on COIL20 Database

In this subsection, we conducted clustering experiment on COIL20 image library. In order to randomize the experiments, we evaluate the clustering performance with different number of clusters (k=6,8,…,18,20). For each given cluster number k (except 20), 10 tests were conducted on different randomly chosen classes; then the average performance as well as the standard deviation was computed over these 10 tests. About the parameter configuration, we report the four matrix factorization based methods (NMF, SNMF, GNMF, and GRNMF_SC) with the number of basis vectors equal to the number of clusters. There are three parameters in GRNMF_SC algorithm: the number of nearest neighbors k in Graph G and the regularization parameters α and λ. We empirically set k=4, α=0.1, and λ=10.The clustering result is evaluated by comparing the obtained label of each sample with the label provided by the dataset. Two metrics, the accuracy (AC) and the normalized mutual information metric (NMI), are used to measure the clustering performance. Please see [10, 21] for detailed definitions of these two metrics. Table 7 shows the clustering results on the COIL20; the mean and standard error of the performance are reported in the table.Table 7
Clustering performance on COIL20 database.
K
AC (%)
NMI (%)
K-means
NMF
SNMF
GNMF
GRNMF_SC
K-means
NMF
SNMF
GNMF
GRNMF_SC
6
71.4 ± 14.3
66.1 ± 9.1
71.2 ± 9.3
82.6 ± 9.3
85.7 ± 8.6
70.1 ± 12.5
71.2 ± 11.2
70.5 ± 9.9
86.6 ± 10.8
87.1 ± 9.2
8
66.4 ± 8.5
65.4 ± 5.3
68.3 ± 6.2
83.0 ± 7.8
85.4 ± 7.0
68.0 ± 7.8
72.8 ± 7.1
74.3 ± 8.5
86.7 ± 8.0
86.4 ± 9.3
10
64.3 ± 7.8
63.5 ± 6.2
65.7 ± 5.6
82.5 ± 6.9
84.3 ± 6.6
68.5 ± 7.2
73.5 ± 8.5
74.5 ± 6.6
85.5 ± 7.5
86.2 ± 6.1
12
63.8 ± 6.9
62.7 ± 5.3
65.2 ± 5.1
80.8 ± 7.9
83.0 ± 5.1
68.7 ± 5.5
72.1 ± 5.6
73.3 ± 7.4
84.7 ± 4.7
87.3 ± 5.0
14
61.2 ± 5.1
61.5 ± 2.7
64.3 ± 3.7
78.9 ± 3.0
82.4 ± 2.9
69.2 ± 3.1
71.8 ± 2.9
72.6 ± 4.8
83.6 ± 4.0
87.5 ± 3.9
16
62.8 ± 5.5
62.2 ± 2.0
65.9 ± 3.4
79.0 ± 3.7
81.9 ± 4.6
70.0 ± 2.8
70.3 ± 2.8
71.6 ± 3.2
83.2 ± 3.0
86.3 ± 2.3
18
62.6 ± 4.9
60.5 ± 2.4
63.2 ± 1.7
77.6 ± 2.7
80.4 ± 2.1
71.2 ± 3.1
71.1 ± 2.4
73.4 ± 1.6
82.5 ± 2.5
86.1 ± 0.4
20
61.5
60.4
63.6
77.2
77.9
73.9
70.3
74.9
85.4
87.2
Avg.
64.3
62.8
65.9
80.2
82.6
69.9
71.6
73.1
84.8
86.8As shown in Table7, our GRNMF_SC always results in the best performances in all the cases. GRNMF_SC aims to enable the learned basis to preserve the intrinsic manifold structure of original data and meanwhile ensure the sparseness of new representations under the basis. The above properties guarantee each image data point can be represented by linear combination of only few key basis vectors, which makes our GRNMF_SC particularly suitable for image clustering. Consequently, by simply using k-means on the low-dimensional sparse representation, GRNMF_SC achieves very impressive clustering performance. In addition, GNMF gets better clustering results compared to SNMF and NMF, while K-means performs the worst among the involved methods.


## 4.1. Recognition Results on ORL and YALE Database

In this part, the face recognition experiment is carried out on the ORL and YALE database. First, to evaluate all methods’ ability to dealing with differentGms for ORL database, a random subset with Gm(G3,G4,G5,G6,G7) is taken with labels to form the training set, respectively, and the corresponding remaining part Pn(P7,P6,P5,P4,P3) with labels is taken to form the testing set. For YALE database, Gm(G4,G5,G6,G7,G8) is taken to form the training set and the corresponding remaining part Pn(P7,P6,P5,P4,P3) is taken to form the testing set. For each given Gm/Pn, we averaged the results over 10 random splits. Tables 1 and 2 show the optimal average recognition rates obtained by NMF, LNMF, SNMF, GNMF, FMD-NMF, and S-GRNMF_SC with the same feature dimension in differentGms over 10 random splits.Table 1
Optimal average recognition rates ±  σ2 on ORL database with different number of training samples of each person (dimensions = 50).
Method
G
3
/
P
7
G
4
/
P
6
G
5
/
P
5
G
6
/
P
4
G
7
/
P
3
NMF
72.8% ± 2.0%
78.8% ± 1.5%
82.6% ± 2.0%
85.0% ± 3.5%
88.0% ± 3.5%
LNMF
61.4% ± 8.0%
65.4% ± 6.0%
67.5% ± 4.0%
71.3% ± 3.9%
74.2% ± 4.0%
SNMF
73.6% ± 1.0%
79.3% ± 1.0%
82.8% ± 2.0%
85.3% ± 2.0%
89.0% ± 1.5%
GNMF
73.9% ± 1.0%
80.9% ± 1.0%
83.8% ± 2.0%
86.2% ± 1.0%
89.5% ± 1.0%
FMD-NMF
72.5% ± 1.0%
82.1% ± 2.0%
87.0% ± 1.0%
88.5% ± 1.5%
92.0% ± 2.0%
S-GRNMF_SC
73.2% ± 2.0%
83.3% ± 3.0%
89.0% ± 2.0%
90.4% ± 1.0%
92.5% ± 2.0%Table 2
Optimal average recognition rates ±  σ2 on YALE database with different number of training samples of each person (dimensions = 50).
Method
G
4
/
P
7
G
5
/
P
6
G
6
/
P
5
G
7
/
P
4
G
8
/
P
3
NMF
62.8% ± 5.7%
64.4% ± 3.5%
67.7% ± 4.0%
76.3% ± 1.0%
80.8% ± 2.0%
LNMF
61.5% ± 1.0%
68.9% ± 1.0%
70.7% ± 1.5%
79.0% ± 2.0%
83.1% ±  2.0%
SNMF
63.6% ± 3.5%
65.3% ± 2.5%
70.0% ± 2.0%
77.7% ± 2.0%
82.2% ±  2.0%
GNMF
63.8% ± 2.9%
66.7% ± 2.0%
72.0% ± 2.0%
80.0% ± 1.5%
83.1% ±  2.0%
FMD-NMF
65.3% ± 2.0%
68.5% ± 1.8%
71.7% ± 3.0%
79.8% ± 3.0%
82.2% ± 3.0%
S-GRNMF_SC
67.0% ± 1.5%
70.2% ± 3.0%
73.3% ± 2.0%
83.3% ± 1.5%
85.4% ±  2.0%Figure1 shows the average recognition rates versus feature dimensions of all the competing algorithms. Note that the optimal average recognition rates are obtained over the whole feature dimensions. The feature dimension is chosen from 0 to 100 with intervals of 10 with different G5/P5s for ORL database and G7/P4 for YALE database.Figure 1
Average recognition rate of NMF, LNMF, SNMF, GNMF, and S-GRNMF_SC versus different feature dimensions on ORL and YALE databases.
(a)
ORL database (48 × 48)
(b)
YALE database (32 × 32)From Tables1 and 2 and Figure 1, it is shown that S-GRNMF_SC algorithm increases about 2% in average recognition rates compared with FMD-NMF algorithm and delivers nearly 4% of improvement recognition rates compared to GNMF and SNMF. In addition, FMD-NMF obtains the next best results, for the reason that FMD-NMF also utilizes the class label information and preserves the manifold structure like S-GRNMF_SC. GNMF and SNMF methods perform comparatively close to FMD-NMF. NMF is slightly worse than SNMF, while LNMF algorithm performs the worst; the reason is LNMF pays main attention to keep the bases orthogonal while ignoring the performance of coefficients; this leads to poor classification performance.


## 4.2. Learning Basis Images from the ORL and YALE Database

In this subsection, we use NMF, LNMF, GNMF, FMD-NMF, and the proposed S-GRNMF_SC algorithms to learn 25 and 49 basis images from the ORL and YALE database, respectively. Then we use the sparseness metric (SP) [24] to measure the sparseness of basis matrix as well as coefficients matrix. The sparseness measure, which is based on the relationship between the L1 norm and the L2 norm, is formularized as(23)SP(H)=N-∑hi/∑hi2N-1,where hi is a column vector of matrix H. If all elements of hi are equal, SP(H) is equal to zero; if hi only contains a single nonzero element, SP(H) is equal to unity. The basis images are shown in Figure 2. The sparseness of basis matrix and coefficient matrix is shown in Tables 3 and 4.Table 3
Sparseness comparison for different NMF models under different levels (r=25, r=49) on ORL database.
Method
Average sparseness on
Average sparseness on
Average sparseness on
Average sparseness on
U (r=25)
V
T (r=25)
U (r=49)
V
T (r=49)
NMF
0.262122
0.295615
0.311064
0.335885
LNMF
0.633281
0.006225
0.705528
0.007179
GNMF
0.264691
0.231159
0.318175
0.305258
FMD-NMF
0.433127
0.220854
0.505354
0.289466
S-GRNMF_SC
0.383589
0.312841
0.468214
0.364870Table 4
Sparseness comparison for different NMF models under different levels (r=25, r=49) on YALE database.
Method
Average sparseness on
Average sparseness on
Average sparseness on
Average sparseness on
U (r=25)
V
T (r=25)
U (r=49)
V
T (r=49)
NMF
0.412778
0.389463
0.469252
0.401235
LNMF
0.703995
0.025648
0.774678
0.027278
GNMF
0.457980
0.396353
0.536095
0.413464
FMD-NMF
0.512505
0.373300
0.605472
0.380108
S-GRNMF_SC
0.607605
0.428920
0.689776
0.446257Figure 2
5 × 5 and 7 × 7 basis images of NMF, LNMF, GNMF, FMD-NMF, and S-GRNMF_SC on ORL and YALE database.
(a)
5 × 5 and 7 × 7 basis images of NMF on ORL and YALE database
(b)
5 × 5 and 7 × 7 basis images of LNMF on ORL and YALE database
(c)
5 × 5 and 7 × 7 basis images of GNMF on ORL and YALE database
(d)
5 × 5 and 7 × 7 basis images of FMD-NMF on ORL and YALE database
(e)
5 × 5 and 7 × 7 basis images of S-GRNMF_SC on ORL and YALE databaseFrom the results, it is clear that the bases obtained by NMF and GNMF are additive, but not spatially localized for facial representations. In contrast, S-GRNMF_SC and FMD-NMF have the following advantages and improvements when compared with them. The bases learnt by S-GRNMF_SC and FMD-NMF are better than NMF and GNMF, since these bases not only reveal the additive property but also capture the discriminant information and preserve the manifold structure. In addition, though LNMF can obtain the spatially localized bases, it does not take the intrinsic structures of the data into account, which is also important in the classification task.


## 4.3. Face Reconstruction on the ORL Database

In this subsection, the reconstruction experiments of NMF, LNMF, GNMF, FMD-NMF, and S-GRNMF_SC algorithms are performed on the ORL database. We selected 4 different types, that is, men’s frontal view with no facial expression (MFV_NFE), men’s frontal view with wearing glasses (MFV_WG), men’s lateral view with smiling facial expression (MLV_SFE), and women’s frontal view with no facial expression (WFV_NFE), from images in the ORL database. The reconstructed images using these algorithms compared with the original ones are presented in Figure3, where the leftmost are the original images, and the images to the right are reconstructed images obtained by NMF, LNMF, GNMF, GRNMF_SC, and FMD-NMF, respectively. It is evident that the reconstruction quality of GRNMF_SC is better than the others’. This observation is validated by computing all methods’ reconstruction residual error through pixel gray value difference between the original and reconstructed images. The residual error is represented by the norm F2 of the residual matrix. The results are shown in Table 5. The reconstruction residual error of GRNMF_SC is the smallest in all cases except the first type. From these results, it is clear that the reconstruction quality by GRNMF_SC is robust to gender and different facial expressions. GNMF and FMD-NMF are next to GRNMF_SC. LNMF scheme performs the worst though it provides smoother reconstructions than other methods.Table 5
Reconstruction residual error of NMF, LNMF, GNMF, FMD-NMF, and GRNMF_SC with 4 kinds of selected images on the ORL.
Method
MFV_NFE
MLV_SFE
MFV_WG
WFV_NFE
NMF
17.09
14.23
40.47
35.29
LNMF
67.91
32.24
44.70
50.33
GNMF
26.53
15.46
31.08
23.42
S-GRNMF_SC
22.65
11.59
25.74
17.36
FMD-NMF
19.34
14.10
38.49
24.77Figure 3
Reconstruction effects by NMF, SNMF, LNMF, GNMF, S-GRNMF_SC, and FMD-NMF. From top to the bottom are MFV_NFE, MFV_WG, MLV_SFE, and WFV_NFE images. Leftmost are the original face images and from second to the last columns are reconstruction effects.
(a)
(b)
(c)
(d)


## 4.4. Occluded Face Recognition on ORL Database

NMF and its variants are parts-based representation algorithms; they can achieve better recognition results than other traditional appearance-based methods (e.g., LPP and LSDA) in the occluded face database. S-GRNMF_SC performs better than other traditional NMF algorithms. In order to highlight the superior advantage of S-GRNMF_SC against other NMF algorithms in the occluded face database, we give the experimental results in what follows. The size of sheltering patch is from 10 × 10, 15 × 15, 20 × 20, and 25 × 25 pixels, respectively, and the position is randomly selected. Figure4 shows the occluded face images.Figure 4
Occluded face samples: the sheltering patch is randomly placed on the faces, and the size is (from left to right) 10 × 10, 15 × 15, 20 × 20, and 25 × 25 pixels, respectively.
(a)
(b)
(c)
(d)Figure5 shows the recognition accuracies versus different feature dimensions with occluding patch size of 10 × 10, 15 × 15, 20 × 20, and 25 × 25 pixels on the ORL database, respectively. Table 6 presents optimal average recognition rates on occluded ORL database with different size of sheltering patch. From Figure 5 and Table 6, we can see that S-GRNMF_SC performs much better than other algorithms; there is about 5% to 20% improvement. The significant improvements are owing to the sparseness and manifold constraints in S-GRNMF_SC. Specifically, S-GRNMF_SC can obtain sparser representation than FMD-NMF; furthermore S-GRNMF_SC maintains more local information than GNMF, and more discriminant and geometrical information than standard NMF, LNMF, and SNMF. The occluding experiment strongly supports the necessity of imposing sparseness and manifold constraint simultaneously.Table 6
Optimal average recognition rates ±  σ2 on occluded ORL database with different size of sheltering patch (dimensions = 50).
Method
10
×
10
1
5
×
1
5
2
0
×
2
0
25
×
25
NMF
80.5% ± 2.0%
74.7% ± 1.5%
69.5% ± 2.0%
62.3% ± 1.0%
LNMF
59.5% ± 5.0%
55.7% ± 4.0%
51.7% ± 4.0%
45.6% ± 3.0%
SNMF
81.8% ± 1.5%
78.2% ± 2.0%
72.5% ± 2.0%
66.3% ± 2.0%
GNMF
82.5% ± 1.0%
79.3% ± 2.0%
73.3% ± 2.0%
68.0% ± 2.0%
FMD-NMF
83.2% ± 2.0%
80.5% ± 2.5%
74.0% ± 1.5%
68.5% ± 2.0%
S-GRNMF_SC
85.5% ± 1.0%
83.5% ± 2.0%
77.5% ± 2.0%
73.2% ± 2.0%Figure 5
Recognition accuracies versus different feature dimensions on ORL database with different occluding patch size.
(a)
Occluding patch size 10 × 10
(b)
Occluding patch size 15 × 15
(c)
Occluding patch size 20 × 20
(d)
Occluding patch size 25 × 25


## 4.5. Clustering Experiment on COIL20 Database

In this subsection, we conducted clustering experiment on COIL20 image library. In order to randomize the experiments, we evaluate the clustering performance with different number of clusters (k=6,8,…,18,20). For each given cluster number k (except 20), 10 tests were conducted on different randomly chosen classes; then the average performance as well as the standard deviation was computed over these 10 tests. About the parameter configuration, we report the four matrix factorization based methods (NMF, SNMF, GNMF, and GRNMF_SC) with the number of basis vectors equal to the number of clusters. There are three parameters in GRNMF_SC algorithm: the number of nearest neighbors k in Graph G and the regularization parameters α and λ. We empirically set k=4, α=0.1, and λ=10.The clustering result is evaluated by comparing the obtained label of each sample with the label provided by the dataset. Two metrics, the accuracy (AC) and the normalized mutual information metric (NMI), are used to measure the clustering performance. Please see [10, 21] for detailed definitions of these two metrics. Table 7 shows the clustering results on the COIL20; the mean and standard error of the performance are reported in the table.Table 7
Clustering performance on COIL20 database.
K
AC (%)
NMI (%)
K-means
NMF
SNMF
GNMF
GRNMF_SC
K-means
NMF
SNMF
GNMF
GRNMF_SC
6
71.4 ± 14.3
66.1 ± 9.1
71.2 ± 9.3
82.6 ± 9.3
85.7 ± 8.6
70.1 ± 12.5
71.2 ± 11.2
70.5 ± 9.9
86.6 ± 10.8
87.1 ± 9.2
8
66.4 ± 8.5
65.4 ± 5.3
68.3 ± 6.2
83.0 ± 7.8
85.4 ± 7.0
68.0 ± 7.8
72.8 ± 7.1
74.3 ± 8.5
86.7 ± 8.0
86.4 ± 9.3
10
64.3 ± 7.8
63.5 ± 6.2
65.7 ± 5.6
82.5 ± 6.9
84.3 ± 6.6
68.5 ± 7.2
73.5 ± 8.5
74.5 ± 6.6
85.5 ± 7.5
86.2 ± 6.1
12
63.8 ± 6.9
62.7 ± 5.3
65.2 ± 5.1
80.8 ± 7.9
83.0 ± 5.1
68.7 ± 5.5
72.1 ± 5.6
73.3 ± 7.4
84.7 ± 4.7
87.3 ± 5.0
14
61.2 ± 5.1
61.5 ± 2.7
64.3 ± 3.7
78.9 ± 3.0
82.4 ± 2.9
69.2 ± 3.1
71.8 ± 2.9
72.6 ± 4.8
83.6 ± 4.0
87.5 ± 3.9
16
62.8 ± 5.5
62.2 ± 2.0
65.9 ± 3.4
79.0 ± 3.7
81.9 ± 4.6
70.0 ± 2.8
70.3 ± 2.8
71.6 ± 3.2
83.2 ± 3.0
86.3 ± 2.3
18
62.6 ± 4.9
60.5 ± 2.4
63.2 ± 1.7
77.6 ± 2.7
80.4 ± 2.1
71.2 ± 3.1
71.1 ± 2.4
73.4 ± 1.6
82.5 ± 2.5
86.1 ± 0.4
20
61.5
60.4
63.6
77.2
77.9
73.9
70.3
74.9
85.4
87.2
Avg.
64.3
62.8
65.9
80.2
82.6
69.9
71.6
73.1
84.8
86.8As shown in Table7, our GRNMF_SC always results in the best performances in all the cases. GRNMF_SC aims to enable the learned basis to preserve the intrinsic manifold structure of original data and meanwhile ensure the sparseness of new representations under the basis. The above properties guarantee each image data point can be represented by linear combination of only few key basis vectors, which makes our GRNMF_SC particularly suitable for image clustering. Consequently, by simply using k-means on the low-dimensional sparse representation, GRNMF_SC achieves very impressive clustering performance. In addition, GNMF gets better clustering results compared to SNMF and NMF, while K-means performs the worst among the involved methods.


## 5. Conclusions and Future Work

In this paper, GRNMF_SC is proposed, which combines the advantages of manifold learning and sparse coding. GRNMF_SC explicitly adds the sparseness constraint on the coefficient matrixVT, which naturally leads to a sparse representation.The target function of our method is easy to propose, while the solving procedures are really nontrivial; in the paper we gave the detailed derivation of solving the target function and also a strict proof of its convergence, which is a key contribution of the paper. We implement GRNMF_SC in both supervised (S-GRNMF_SC) and unsupervised versions. S-GRNMF_SC increases the recognition rates when comparing with standard NMF, SNMF, LNMF, GNMF, and FMD-NMF, especially in occluded face recognition. Unsupervised GRNMF_SC also improves the clustering performance compared to recent popular clustering algorithms.It should be noted that, because the proposed GRNMF_SC method has a fully multiplicative update rules and two parameters, one should carefully select the two parameters to strike a balance between the weight of sparseness and discrimination according to the demands of real applications.The future work may continuously investigate different NMF variants and find out the general rules. One also needs to use the advanced NMF method [25] to solve the problems in other real applications. For example, in [26], researchers successfully used the NMF algorithm solving the problem in neurorehabilitation engineering. Although NMF algorithm has emerged for several years, it is still a very important researching direction in the next few years.



---

*Source: 239589-2015-03-15.xml*