Robust Dictionary Learning with Capped l1-Norm

1 Introduction

Dictionary learning [Tosic and Frossard, 2011] and sparse representation [Olshausen and Field, 1997] are important tools for computer vision. Dictionary learning seeks to learn an adaptive set of basis elements (dictionary) from data instead of predefined ones [Mallat, 1999], so that each data sample is represented by sparse linear combination of these basis vectors. It has achieved start-of-the-art performance for numerous image processing tasks such as classification [Raina et al., 2007; Mairal et al., 2009b], denoising [Elad and Aharon, 2006], self-taught learning [Wang et al., 2013b], and audio processing [Grosse et al., 2007]. Unlike principal component analysis, dictionary learning does not impose that the dictionary be orthogonal, hence allow more flexibility to represent data.

Usually, dictionary learning is formulated as:

In this formulation, X ∈ Rd×n is the data matrix whose columns represent samples, A ∈ RK×n is the new representations of data and the matrix D ∈ Rd×K contains K basis vectors to learn. To prevent the ℓ2 norm of D being arbitrarily large which would lead to arbitrarily small values in the columns of A, it is common to constraint the columns have ℓ2 norm less than or equal to 1. Hence, D is in the following convex set of matrices:

∗Corresponding Author. This work was partially supported by NSF IIS-1117965, IIS-1302675, IIS-1344152, DBI-1356628.

The dictionary learned is the foundation for sparse representations. Dictionary with good expressive ability is the key to achieve good performance. It is well known that the quadratic loss function is not robust to outliers. To train the dictionary, a large amount data will be used, and outliers will be included in the training data unavoidably. Hence it is necessary to learn dictionary resistant to outliers.

To be robust to outliers, the quadratic loss function could be replaced by an loss function that are not sensitive to outliers, e.g. ℓ1 norm loss or Huber loss. In this paper, we use capped ℓ1-norm based loss function lε(u) = min(|u|, ε), where ε is a parameter. It is illustrated in Fig. 1. This loss function treat u equally if |u| is bigger than ε. Hence, it is more robust to outliers than ℓ1 norm. Unfortunately, this loss function is not convex. In this paper, we propose an efficient algorithm to find the local optimal solutions. And we will also provide theoretical analysis of this method.

2 RelatedWork

In this section, we present a brief review on dictionary learning methods as follows.

Since the original dictionary learning model (1) is NP-hard, the straightforward way to find dictionary is to adopt greedy strategy. K-SVD [Aharon et al., 2006] tried to solve the following model:

where di is the ith column of matrix D. The K-SVD is an iterative method that alternates between sparse coding of the examples based on the current dictionary and a process of updating the dictionary atoms. The columns of dictionary are updated with SVD sequentially, and the corresponding coefficients are updated with any pursuit algorithm. The K-SVD algorithm showed good performance on image denoising. As extensions of K-SVD, LC-KSVD [Jiang et al., 2013] and discriminative K-SVD [Zhang and Li, 2010] introduced label information into the procedure of learning dictionaries. Hence the dictionaries learned are more discriminative.

Except for adopting greedy strategy to solve problems with l0 constraints, the original problem can be relaxed into the following traditional dictionary learning problem with ℓ1 regularization:

It is convex separately with respect to D and A, a ℓ1 regularized least squares problem and a ℓ2 constrained least squares problem are needed to be solved iteratively to find the solutions. In [Lee et al., 2007], an feature-sign search algorithm for learning coefficients, and a Lagrange dual method for learning the bases are proposed to compute the dictionary and corresponding representations. An online algorithm was proposed to solve it efficiently in [Mairal et al., 2009a]. The method mentioned above all use quadratic loss functions to measure the reconstruction errors, hence these methods are not robust enough to outliers.

In order to learn dictionary robustly, Lu et al. proposed online robust dictionary learning (ORDL) [Lu et al., 2013], which uses ℓ1 loss function and ℓ1 regularization term that could be expressed as

It updates dictionary and representations alternately in an online way. For visual tracking, Wang proposed online robust non-negative dictionary learning [Wang et al., 2013c], which uses the Huber loss function. In [Wang et al., 2013a], the semi-supervised robust dictionary learning model was proposed by solving the ℓp-norm based objective.

3 Proposed NewAlgorithm

To facilitate the presentation of our method, we describe the notations in the following subsection.

3.1 Notations

Throughout this paper, the following definitions and notations are used. We use bold upper letters for matrices, bold lower letters for vectors and regular lower letters for elements. For vector a = (a1, a2, · · · , am)T ∈ Rm, let ‖a‖1 = ∑mi=1 |ai| be the ℓ1-norm of a. Similarly, we define ‖A‖0 as the number of nonzero elements in matrix A and ‖A‖1 = ∑ ‖ai‖1 be the ℓ1 norm of matrix A.

3.2 Robust dictionary learning

Capped ℓ1-norm has been used in [Zhang, 2010; 2013] as a better approximation of ℓ0-norm regularization. An extension capped-ℓ1,1 regularization was proposed in the multi-task feature learning setting [Gong et al., 2013]. In this paper, we use capped ℓ1-norm as a robust loss function.

For dictionary learning, our goal is to find a set of high quality atoms. An straightforward way is to use ℓ1 loss function. To provide better robustness, we go further to use capped ℓ1-norm loss function. As illustrated in Fig 1, the objective values of capped ℓ1-norm loss does not increase any more if |u| is larger than ε. Therefore, capped ℓ1-norm loss is more robust than ℓ1-norm loss. We use the same constraints for dictionary and the objective function of our roust dictionary learning with capped ℓ1-norm is expressed as:

From this objective function, we can see that if ε is set as ∞, the above objective function becomes ℓ2,1-norm with the same constraints.

We define f(A) = ‖A‖1, which is a convex function. And define a concave function ¯L(u) = min(√u, ε) where u > 0 and g(D, a) = ‖x - Da‖22 . We have:

Our objective function is sum of a convex function and a concave function. According to the re-weighted method proposed in [Nie et al., 2010; 2014], it can be solved by updating D,A and auxiliary variables si with following updating rules:

The whole iterative re-weighted method is listed in Alg. 1.

The subproblem (8) is similar to the traditional dictionary learning. The only difference lies in the fact that samples are not treated equally. It is weighted dictionary learning. From the updating rule for si, we can see that the samples with lower reconstruction errors have higher weights, which is very intuitive for learning dictionary robustly.

The subproblem (8) is convex separately with respect to D and A. We adopt the same strategy as solving traditional dictionary learning. We solve it by updating D and A alternately. With A fixed, the objective function becomes:

which is equivalent to:

where zi = √sixi and ci = √siai. To solve the above problem, we update D column by column which is similar to the traditional dictionary learning. The algorithm we use is adopted from [Mairal et al., 2009a], which is described in Alg. 3.

With D fixed, the objective of (8) becomes:

which can be decomposed into n independent problems as follows:

If si ̸= 0, this problem can be transformed into the following LASSO problem:

which could be solved efficiently. The algorithm to solve weighted dictionary learning is summarized in Alg. 2.

During the stage of training dictionary D, if si is 0, the corresponding representation ai will be a zero vector. Hence, when training D, our method does not find codings for outliers. However, the outliers in training D stage might not be outliers for classification tasks. Hence, we let the classification algorithm to decide how to use the codings of the outliers. With the learned D, in order to get the codings for outliers, we just run Alg. 1 with setting ε as ∞ and omit the D updating step (step 1 in Alg. 2) to learn the representations for both training data and testing data with the same λ. In fact, we are solving a dictionary learning problem with ℓ2,1-norm loss function.

Algorithm 1 Robust dictionary learning with capped ℓ1-norm

input: Data matrix X, dictionary size K, λ and ε.

Initialize D, A and si = 1 for i = 1, 2, · · · , n.

repeat

1. Solve subproblem (8) with algorithm 2
2. Update si for i = 1, · · · , n as (9)

until Converge

output: D and A

3.3 Convergence analysis

Theorem 3.1. The algorithm described in Alg. 1 will decrease the objective value of (6) in each iteration until it converges.

Proof. We define h(w) = w2 , and denote u = ‖x -Da‖22 and ¯L(u) = min(√u, ε). The capped ℓ1-norm loss function min(‖x - Da‖2, ε) could be re-written as:

Algorithm 2 Weighted dictionary learning

input: Data matrix X, initial dictionary matrix D0 and representation matrix A0, λ and weight vector s.

Initialize D = D0 and A = A0

repeat

1. Update D with algorithm 3.
2. Update ai for i = 1, · · · , n as

until Converge

output: D, A

Algorithm 3 Dictionary update

input: Data matrix X, dictionary matrix D, representation matrix A and weight vector s.

repeat

for j = 1 to K do

Update the j-th column of D:

end for

until Converge

output: D

where L∗ (s) is the concave dual of ¯L(u) defined as:

Plug in ¯L(u) and it is easy to find that:

Therefore, the capped ℓ1-norm loss could be expressed as:

where

Hence, the objective function (6) is equivalent to the following objective:

which can be re-written as:

where we denote:

Therefore, the algorithm described in Alg. 1 can be seen as a two stage optimization method:

Updating D and A stage: D and A are updated by solving:

which is equivalent to:

The updated D and A decrease the objective values of (25). Hence, they also decrease the objective values of (24).

Updating si stage: The auxiliary variable s are updated by solving:

which is equivalent to n independent problems

Both stages will decrease the value of the objective function (21), hence our algorithm also decrease the value of the original objective function (6) and is guaranteed to converge.

4 Experimental Results

In this section, we analyze and illustrate the performance of our method on real word datasets.

4.1 Preliminary study on natural image patches

First, we present a preliminary analysis of our method on natural image patches. In our method, λ mainly controls the sparsity of representations and ε mainly controls the number of outliers identified by the algorithm. ε is related to the residuals of representations. If the residual of a sample is larger than ε, it is not used to train the dictionary, since the corresponding s is zero. We set ε as infinity first to get the distribution of the residuals. We use this distribution as an estimation of the distribution of residuals with optimal D and A. We set ε such that a fraction of samples are seen as outliers. In this experiment, we set the fraction of outliers as 0.05 and λ = 0.1 empirically. The values of objective function during iterations are presented in Fig. 2. We can see that our method converged in only 22 iterations. The bases learned on natural image patches by our method is shown in Fig. 3.

iteration

Figure 3: Learned 1,024 bases images bases (each 14 × 14 pixels) on 10,000 natural images patches.

4.2 Face recognition without occlusion

In this subsection, we provide the experimental results on face recognition tasks without synthetic occlusion on extended Yale B dataset [Georghiades et al., 2001] and AR face dataset [Martinez, 1998].

Extended Yale B dataset The extended Yale B database [Georghiades et al., 2001] contains 2,414 images of 38 human frontal faces under 64 illumination conditions and expressions. There are about 64 images for each person. The original images were cropped to 192 × 168 pixels. Some samples are shown in Fig. 4(a). We do not perform any preprocess on the images. Following [Wright et al., 2009], we project each face image into a 504-dimensional feature vector using a random matrix. We split the database randomly into two halves. One half which contains about 32 images for each person was used for training the dictionary. The other half was used for testing.

In the practical implementation of our method, we first set ε as infinity and choose the best λ with cross validation. Then we fix λ and choose ε.

For face recognition, we compared our method with a few start-of-the-art methods, including traditional dictionary learning [Mairal et al., 2009a], K-SVD [Aharon et al., 2006], LC-KSVD1 and LC-KSVD2 [Jiang et al., 2013], D-KSVD [Zhang and Li, 2010] and ORDL [Lu et al., 2013]. The dictionary size is 570 for all methods, which means 15 items for person on average. The parameters for these methods were selected by cross validation. We ran all methods on 10 different splits of training and testing set. The results are summarized in Table 1. We can see that our method achieved the best performance. The reason that ORDL did not perform well might be the dictionary and representations trained with ℓ1-norm loss function are not suitable for classification tasks.

We show that our method is robust when training dictionary. Recall that, in our method si = 0 means that the ith sample is recognized as outlier and not used in training the dictionary. In running on one random split, our method found 20 outliers, which are all shown in Fig. 5. We can see that most of the outliers found by our method are with extreme illumination, which will effect the quality of bases.

AR face dataset The AR face dataset [Martinez, 1998] consists of over 4,000 color images from 126 individuals. For each individual, 26 pictures were taken in two separate sessions. Compared to the extended Yale B dataset, as shown in Fig. 4(b) 1 , the AR face dataset includes more facial variations, including different illumination conditions, different expressions, and different facial disguises (sunglasses and scarves). Following the standard evaluation procedure from [Wright et al., 2009], we used a subset of the database consisting of 2,600 images from 50 male subjects and 50 female subjects. For each person, 20 images were randomly selected for training and the remaining images are for testing. Each face image is cropped to 165 × 120 and then projected into a 540-dimensional feature vector.

Similar to the experiments on Yale B dataset, we also ran all methods in 10 different splits of training and testing set. The results are presented in Table 2. We can see that our method achieved the best performance among all dictionary learning algorithms. We show the 17 outliers found by our algorithm in Fig 6. We can see that these outliers are faces with glasses or scarves. Our algorithm identified these faces as outliers that will hurt the quality of dictionary and did not use them in the training process.

4.3 Face recognition with occlusion

In order to study the property of robustness to outliers, we carried out experiments on extended Yale B dataset with synthetic outliers. If the samples for training the dictionary contain outliers, traditional dictionary learning will try to find dictionary that could express these outliers. But it is of no use to express the outliers, hence the quality of dictionary will be effected for traditional dictionary learning. In this experiment, we generate outliers by adding block occlusion. Other ways of generating outliers will also lead to the similar phenomena described below.

1 We use grayscale images in our experiments.

We selected a fraction of images (outlier ratio) from training set, then we added block occlusion of size 96 × 96 into these images at random positions. Some samples are shown in Fig. 7. We set outlier ratio as 10%, 20%, 30% and 40% to get 4 different datasets with synthetic outliers in the training sets. The images from testing sets are not added any occlusions. Under this setting, the effect on the performance of classification will come from the quality of dictionaries. Similar to the experiments we have done above, we also ran experiments on 10 different datasets and the average accuracies are reported in Table 3. We can see that the classification accuracies of all methods decreased as the outlier ratio increased. Compared with performances without block occlusion in Table 1, the performance of traditional dictionary learning dropped a lot (from 95.70 to 90.00 with 10% outliers ). But our method did not drop so much (from 96.91 to 96.29 ). And our method also performed the best on all datasets. Hence we can conclude that our capped ℓ1-norm loss does provide resistance to such kind of noise.

The outliers found by our algorithm from an synthetic dataset with 10% corruption are shown in Fig. 8. We can see that most outliers are images that are too dark or corrupted and are difficult to recognize. In our method, the dictionaries were trained without these samples, hence they were better than dictionaries trained in other ways, which can be proved from the comparisons of performances in Table 3.

5 Conclusion

In this paper, we presented a robust dictionary learning model based on capped ℓ1-norm and an efficient algorithm to find local solutions. One important advantage of our method is its robustness to outliers. By iteratively assigning weights to samples, our algorithm succeeded in finding outliers and reduced their effects on training the dictionaries. The proposed method was extensively evaluated on face recognition jobs on different real word datasets and synthetic datasets. The experimental results demonstrated that our method outperforms previous state-of-the-art dictionary learning methods.