Low-rank representations with incoherent dictionary for face recognition

Face recognition remains a hot topic in computer vision, and it is challenging to tackle the problem that both the training and testing images are corrupted. In this paper, we propose a novel semi-supervised method based on the theory of the low-rank matrix recovery for face recognition, which can simultaneously learn discriminative low-rank and sparse representations for both training and testing images. To this end, a correlation penalty term is introduced into the formulation of our proposed method to learn an incoherent dictionary. Experimental results on several face image databases demonstrate the effectiveness of our method, i.e., the proposed method is robust to the illumination, expression and pose variations, as well as images with noises such as block occlusion or uniform noises.


Introduction
Face recognition (FR) is an interesting and popular issue in the communities of computer vision and pattern recognition, which plays an important role in $ Fully documented templates are available in the elsarticle package on CTAN.
practical applications, e.g., security monitoring and access control. Reducing the dimensionality of the face images is a simple yet effective idea for FR, classical methods like Eigenfaces [1], Fisherfaces [2], Laplacianfaces [3] and their extensions [4,5,6]. With the efforts of the researchers, local discriminant embedding (LDE) [7] and many other methods have been successfully applied in FR. On controlled datasets many face recognition algorithms can achieve superb performance. Unfortunately, they cannot perform well in some real-world situations. According to [8] and [9], the key point to solve the problem is to handle variations in illumination, images misalignment, and occlusion in the testing images simultaneously.
In recent years, the sparse-representation-based classification (SRC) [10] has become very popular in FR. The key idea of SRC is to represent an input sample as a sparse linear combination over all the training samples, in which the 1 -norm is usually used as a sparsity constraint. The results in [10] on FR are promising, and SRC is also robust to face occlusion and corruption in the test images. Nevertheless, the training images should be well aligned in SRC.
To deal with face misalignment, an improved method is presented in [8]. To counteract outliers such as noises in FR, Yang proposed a modified SRC-based framework [11,12]. Unfortunately, the above methods cannot handle well the situation when both training and testing samples are corrupted. To further assess the robustness of sparse representation based recognition algorithms, this problem should be addressed.
According to traditional subspace theory, face images of the same class are often lie in the same low-rank subspace [13,14,15], but due to illumination changes, expression or pose variations and other issues, the actual face images often do not maintain the low-rank structure, which will affect the recognition performance. Recently, low-rank matrix recovery (LRMR), has been successfully applied to FR [13], LRMR can obtain the low-rank data even from the corrupted data. It can efficiently remove sparse noises like illumination changes and occlusions in corrupted face images. Yin et al. [16] presented a new method called low rank matrix recovery with structural incoherence and low rank pro-jection (LRSI LRP) which can correct the corrupted test images with a low rank projection matrix. Zhao et al. [17] developed a discriminative low-rank representation method for collaborative representation-based (DLRR-CR) robust face recognition. Chen et al. [18] proposed a robust low-rank recovery algorithm (RLRR) with a distance-measure structure for face recognition. For the recognition problem, label information should be incorporated to learn discriminative dictionary. Chen et al. [19] adopts the low-rank recovery technique to recover the clean low-rank data matrix from the training data class by class and a structural incoherence term is introduced to enforce the resulting lowrank dictionary for each class to be independent, then the clean data matrix is employed as dictionary for SRC to classify test data. Ma et al. [20] proposed a discriminative low-rank dictionary learning method for FR. The proposed algorithm tries to optimize the sub-dictionaries for each class to be low-rank. In order to learn a dictionary which is not only low-rank but also discriminative, Li et al. [21] applied the constraint on the coding coefficients to make the ratio of the within-class scatter to the between-class scatter be small. However, all of them explore structural information class by class, which cannot capture the global structure. To explore the global structure information among all the training images, Zhang et al. [22] proposed a discriminative, structured lowrank method. It incorporates a code regularization term with block-diagonal structure which can regularize images from the same class to have the same representation to learn discriminative dictionary. However, it is not usually the case. The fact is that face images which are from the same class usually lie in the same subspace and have relevant representation, but the representation is not necessarily the same. To overcome the defect, Li et al. [23,24] proposed a semi-supervised framework to learn robust face representations with classwise block-diagonal structure. It can learn robust representations of training and testing images simultaneously and capture classwise block-diagonal structure with a classwise regularization term at the same time. It can achieve significant performance gains even when both the training and testing samples are corrupted.
Prior work demonstrated that high-quality dictionary can greatly improve the performance of sparse representation approaches [11,12,13,19]. The researchers have made many efforts to learn a good dictionary [19,20,21]. The dictionary learning techniques always focus on the reconstruction accuracy and discriminative power of the dictionary. For example, in [20] and [21] the relationship between two dictionaries for different classes was addressed. Lin et al. [25] proposed an incoherent dictionary learning model that maximizes the incoherence of basis atoms in one single output dictionary, and the experimental results demonstrated the advantages of incoherence constraint.
In this paper, a novel semi-supervised method based on the theory of lowrank matrix recovery is proposed for FR, which focuses on handling the situation that both the training and testing samples are corrupted. Meanwhile, inspired by [25] we explicitly incorporate a correlation penalty in the dictionary learning model to make the dictionary more discerning. The representation learning process is shown in Fig. 1. Our method has several advantages which are summarized as follows.
• We adopt a semi-supervised framework to learn face representation with incoherent dictionary, which can simultaneously learn low-rank and sparse representations of both training and testing images.
• Furthermore, our proposed method is robust to the case that both training and testing images are badly corrupted. We conducted some experiments under the scenarios where samples are corrupted like in Fig. 2.
• In addition, incoherent dictionary with desirable reconstruction and discrimination capability can be learned by the proposed approach.
The rest of this paper is outlined as follows. First, we briefly review related work 0n the low-rank matrix recovery and incoherent dictionary learning in Section 2. Section 3 presents our method. The optimization process based on the inexact Augmented Lagrange Multiplier method for our model is given in Section 4. Section 5 illustrates the classification technique. Computational complexity of our proposed method is presented in Section 6. Experimental results on several face image databases and corresponding discussions are given in Section 7. Finally, Section 8 concludes this paper.

Related Work
First, we summarize some notations. Throughout this paper, notations with a bar denote symbols of training images, while notations with a hat denote symbols of testing images. LetȲ = Ȳ 1 ,Ȳ 2 , . . . ,Ȳ C ∈ R d×n be the feature matrix which is composed of training images of C classes, and the feature matrix Ŷ = ŷ 1 ,ŷ 2 , . . . ,ŷ ns ∈ R d×ns is composed of n s testing images. Thus Y = Ȳ ,Ŷ is the feature matrix of the whole database, where each column of Y denotes the feature of an image. Each image of Y can be coded as a linear combination of the base elements of dictionary D ∈ R d×m , i.e.
where X = X ,X , andX corresponds to the representation matrix of training images, whileX corresponds to the representation matrix of testing images.

Low-Rank and Sparse Representation
Suppose we are given a set of corrupted images from multiple classes, now the problem is to learn robust representations of training and testing images simultaneously. Low-rankness is an appropriate criterion to capture the low dimensional structure from the high-dimensional data [13]. To obtain the clean database Y, learning low-rank representations can be solved as follows, Effectiveness of low-rank and sparse representation for the classification problem has been demonstrated in [19] and [26].
As we know from [13] and [27], low-rank model can reveal the subspace structure of data, sparse representation has been shown to achieve promising performance in FR [10,28,29]. Taking advantage of low-rank and sparse representation is very meaningful, and low-rank and sparse representation for the classification problem is very effective [22,30]. Li et al. [24] imposed both low-rank and sparse constraints on the representation matrix, the method is called learning low-rank and sparse representation (LRRS) for FR, this model is formulated as follows, As the above problem is non-convex, the common way is to substitute the 1norm for 0 -norm and the nuclear norm for the rank function. Therefore, the optimization problem (3) is relaxed into the following problem, The nuclear norm X * (i.e., the sum of singular values), · 1 is defined as the sum of the absolute values of entries in the given matrix, λ and β control the sparsity of sparse noise term E and sparse representation term X, and D is the dictionary that linearly spans the data space.

Incoherent Dictionary Learning (IDL) model
The quality of dictionary is critical for FR, especially when training and testing samples are corrupted, high-quality dictionary can greatly improve the performance of sparse representation approaches [11,12,13,19]. Lin et al. [25] proposed an incoherent dictionary learning model, which maximizes the incoherence of basis atoms in one single output dictionary to learn a discriminative dictionary. The correlation measure of a dictionary D can be defined as, where I ∈ R m×m is an identity matrix, we can see from the formula (5) that the correlation measure is zero when the columns of dictionary D are orthogonal, in which case the dictionary D is the most irrelevant.

Low-Rank Representations with Incoherent Dictionary
The experimental results in [23] and [24] verified that the semi-supervised learning method can effectively deal with the case that both the training and testing samples are corrupted. Inspired by the work of [23] and [24], we also exploit the semi-supervised learning framework. We propose a new method of low-rank representations with incoherent dictionary (LRRID) for FR. Finally, the objective function is proposed to learn the sparse and low-rank representation with the incoherent dictionary by explicitly incorporating a correlation penalty into the dictionary learning model, There are three regularization parameters (λ > 0, β > 0 and γ > 0) that reflect relative contributions of each term.

Optimization
By introducing two auxiliary variables J and L, we convert problem (6) into the following equivalent optimization problem, The optimization problem (7) can be solved based on the Augmented Lagrange Multiplier (ALM) method [31], so we adopt the inexact ALM method for efficiency in this paper. The augmented Lagrangian function of problem (7) is as follows, where T 1 , T 2 , and T 3 are Lagrangian multipliers and µ > 0 is the penalty parameter, and A, B = trace A T B . We solve problem (8) iteratively by updating J, X, L, E and D once at a time, and the detailed procedures are as follows.
Updating J: Fix the other variables and solve the following problem, where U, Σ, V T = SVD X k + T k 2 µ k and S [·] is the soft-thresholding (shrinkage) operator defined as follows, Updating X: Fix the other variables and solve the following problem, The optimal solution to (11) is given by Updating L: Fix the other variables and solve the following problem, Updating E: Fix the other variables and solve the following problem, Updating D: Fix the other variables and solve the following problem, The optimization problem (15) can be solved via the first-order gradient descent method [26,32]: where and F (D q ) is the gradient of F (D q ) with respect to D q , parameter η is the step size, and Π D is the projection function which maps each column to the 2 -norm unit ball. More specifically, the dictionary is learned iteratively by finding the local minimum along the gradient direction based on the small step size and normalizing each column vector until convergence. The optimization process of (8) is summarized in Algorithm 1.

Classification
To classify the test data, we employ a linear classifier in the testing phase as in [24]. The coefficientsX for training samples andX for testing samples can be derived through Algorithm 1. We can learn a linear classifier W based on the coefficients of training samples and their labels like [33], where H is the label matrix of training samples, η is the weight of regularization term. Clearly, the formulation (19) is a convex problem, which is solved directly by setting the partial derivatives with respect to W to zero, and the solution is given by Then label for test sample j is given by: where i * is corresponding to the classifier with the largest output.

Computational Complexity
The overall computational complexity of our method is O md (n t + n s ) + m 3 , where m is the number of the bases, d is the feature dimension, n t represents the number of training samples, and n s represents the number of testing samples. The computational complexity of our method is linear with the sample number. In comparison, the sparse representation based recognition methods in [10] and [20] have computational complexity of O m 2 dn s [30], which are slower than our method when n t < (m − 1) n s and m < dn s . Generally, the overall computational complexity of [24] is similar to that of ours.

Experiments and Analysis
We evaluate our approach on three public databases: the ORL database [34], the Extended Yale B database [35,36], and the AR database [37]. Some sample images from these databases are shown in Fig. 3. We test the robustness of LRRID when both training and testing images are corrupted, including block occlusion, illumination change, pose variation, expression change, pixel corruptions and uniform noises, respectively. We compare our method LRRID with some state-of-the-art methods including its special case (LRRS), which are enumerated as follows, (1) LRRID: It is to learn discriminative low-rank and sparse representations for both training and testing images simultaneously in a semi-supervised framework with the incoherent dictionary. The objective function is shown in formulation (6).
(2) LRRS [24]: It is to learn low-rank and sparse representations. The dictionary is composed by the training samples. The objective function is shown in formulation (4).
(3) RCBD [24]: It is to learn representation of training images, testing images and discriminative dictionary simultaneously in a semi-supervised framework with classwise block-diagonal structure regularization to the training images.
(4) DLRD SR [20]: It is to learn discriminative low-rank dictionary class by class, and sparse representation based classification method is employed with respect to the learned dictionary.
(5) SRC [10]: It is to learn sparse representation with the dictionary which is composed of the training samples. Specially, SRC indicates the case that the whole training samples are used as the dictionary. SRC* indicates the case that the dictionary size is the same as ours.
It is worth noting that our method and the work of [24] both adopt the semi-supervised framework, so the experimental results of RCBD have reference value.

ORL Face Database
The ORL database [34] contains 400 face images of 40 people in total, 10 images for each subject. The face images are taken under different lighting conditions, varying facial expressions and facial details, some example images are shown in Fig. 3 (a). Following the protocol in [24], for each class, we randomly  Table 1.   accuracy all the time, our method shows high robustness to the severe corruption like block occlusion, and achieves significant improvement. We can find that our method has stronger identification capability than LRRS by utilizing the incoherent dictionary. The recognition accuracy shows that the performance of our method is better when both training and testing face images are badly corrupted. To some extent, it validates that the incoherent dictionary contains more discriminating information. It also demonstrates that high quality dictionary is demanded for learning discriminative representation when both training and testing face images are badly corrupted.
We present some examples of decomposition results in Fig. 4 with 20% block occlusion. As shown in Fig. 4, the top five images are original images with 20% block corruption, while the second row is the learned incoherent dictionary (D) corresponding to the testing images, the third row denotes the low-rank recovery images (DX) and the bottom five images are the corresponding sparse noise (E) including block corruption, facial expression, and pose changes.

Extended Yale B
The Extended Yale B [35,36] dataset contains 38 subjects with 2414 face images, they are taken under different lighting conditions, Fig. 3  database. We perform 10 times for each experiment and the average recognition accuracy is shown in Table 2. We can see that our approach achieves the best results and outperforms the state-of-the-art method RCBD significantly. The method of RCBD does not have a superb performance when the dimensionality is low, it may lose some structure information. The recognition accuracy of DLRD SR is not very high when the dimension is low, while our method has better performance. After dictionary learning, our method outperforms LRRS by 1.83% on average. The experimental results validate the effectiveness and robustness of our method when face images are corrupted by illumination variations.

AR Face Database
The AR face database [37] includes over 4000 face images for 126 individuals. Following the protocol in [24], a compact dictionary with 5 items for each class is preferred under different scenarios. And the parameters are set as fol-lows, λ = 0.1, β = 0.1 and γ = 0.0001 on the AR database. We perform 10 times for each experiment and the average recognition accuracy is listed in Table 3.   to the other classes. Fig. 7 demonstrates that the face images can be properly represented, and it also validates the effectiveness of the learned dictionary by our method.

Conclusion
In this paper, we proposed a new face recognition method based on the semisupervised framework, in which the incoherent dictionary is introduced to simultaneously learn the discriminative low-rank and sparse representations for both training and testing images. The research indicates that the proposed method can learn robust representations of training and testing images simultaneously even when both training and testing images are badly corrupted. Furthermore, the new method integrates the correlation penalty into the dictionary learning model which can make the dictionary more discerning. All the updating formulas are derived by using the inexact ALM algorithm. The experimental results confirm that our proposed method is effective and robust, achieving state-ofthe-art performance especially when both the training and testing samples are contaminated, including illumination changes, occlusion and pixel corruption.
Parameter selection is a nontrivial task in pattern classification, and there are some parameters in our proposed method, how to choose the best setting parameters in our method is a problem to be further investigated in our future work.  Update J by (9).