Scalable Block-Diagonal Locality-Constrained Projective Dictionary Learning

1 Introduction

Sparse Representation (SR) has delivered impressive results in applications of pattern recognition and data mining [Tropp and Gillert, 2010]; Jiang et al., 2016; Zhang et al., 2016; [Elad and Aharon, 2006]. SR by dictionary learning has been widely-used for reconstructing data by a linear combination of a few items in a dictionary [Jiang et al., 2013]. That is, the dictionary plays a crucial role in the process of SR. But how to obtain a desired dictionary from data is still challenging.

Due to the fact that most high-dimensional real data can be sparsely represented by the representative samples of a class in a lower-dimensional manifold [Wright et al., 2009], the sparse l0/l1-norm constraint on coefficients has been widely used in existing Dictionary Learning (DL) settings [Mairal et al., 2010; Jiang et al., 2016; Zhang and Li, 2010; Li et al., 2019]. Existing algorithms can be divided into unsupervised and supervised ones [Jiang et al., 2013]. Unsupervised DL models focus on minimizing the sparse reconstruction error to obtain a dictionary, e.g., [Wright et al., 2009; Aharon et al., 2006; Wang et al., 2010], among which K-Singular Value Decomposition (KSVD) is one most representative method to generalize K-means clustering and obtain an over-complete dictionary from whole training set [Aharon et al., 2006]. Note that KSVD only requires that the learned dictionary to well reconstruct the training data, thus it is not suitable for classification. Based on SR, [Wright et al., 2009] proposed a Sparse Representation-Based Classification (SRC) method that uses entire training set as dictionary to learn the sparse codes by l1-norm minimization. But, obtaining codes from a large dictionary is computationally expensive. It is also worth noting that some researches [Jiang et al. 2013; Gu et al.2014] have demonstrated that dictionary constructed via supervised learning tends to yield better discriminative performance.

One popular strategy for the supervised DL methods is to compute a shared dictionary for all classes. To enhance the classification performance, most existing models incorporate certain discriminative information to force the coefficients to be discriminating [Jiang et al., 2013; Yang et al., 2014]. For example, a classification error was incorporated into KSVD so that classification and representation performance can be jointly improved [Zhang and Li, 2010]. In [Jiang et al., 2013], a binary sparse code matrix over class labels was introduced to encourage intra-class samples to have similar sparse codes. The other supervised type is to learn a structured dictionary to promote discrimination between classes [Gu et al., 2014; Yang et al., 2014; Ramirez et al., 2010]. [Gu et al., 2014] extended the conventional synthesis dictionary learning to joint synthesis and analysis dictionary pair learning. [Yang et al., 2014] used a Fisher discrimination criterion with l1-norm sparsity for the sparse coding to enhance the discriminating powers of learnt dictionary and coding coefficients.

It is worth noting that aforementioned methods still suffer from certain shortcomings. First, existing methods usually use the costly l0 or l1-norm sparsity constraint to obtain sparse codes for representation. But the use of l0/l1-norm constraint brings huge computation burden and thus makes the training phase inefficient. Second, for classification existing methods usually have two separable steps: coding and classification. Concretely speaking, given a new test sample, they have to obtain its coding coefficient using trained dictionary firstly under a sparsity constraint, and then classify it based on the pre-obtained codes, which is not straightforward and costly. It is worth noting that Projective Dictionary Pair Learning (DPL) [Gu et al., 2014] computes an analysis dictionary to obtain group sparse coefficients without l0/l1-norm constraint, and it can reduce the time complexity in training phase in the case that the training set is small. But it uses complementary data matrix of the data l X of each class l in training set X to learn the sub-dictionary l D of each class l, which means that lots of training time are needed when the size of training set is large. In addition, DPL did not consider the classification issue to train a classifier jointly, i.e., it is indeed a two-stage model, hence its performance may be degraded in reality.

In this paper, we propose a new scalable DL framework to overcome the drawbacks mentioned above. The major contributions of this paper are described as follows:

(1) A novel scalable block-diagonal Locality-Constrained Projective Dictionary Learning (LC-PDL) framework is technically proposed. LC-PDL aims to calculate a structured dictionary and codes of each class separately by optimizing each sub-dictionary to reconstruct intra-class data to obtain block-diagonal representations. To improve the scalability, we avoid using costly l0/l1-norm and complementary data matrix when seeking the sub-dictionary l D of each class l, which can potentially save lots of training time in large-scale cases. Besides, we avoid using extra time-consuming sparse reconstruction process with well-trained dictionary for each new data to save testing time. Since real data usually contain noise and outliers, to keep the locality, we add a Laplacian regularization over learned dictionaries to encourage "close" points to have similar codes [Li et al., 2015].

(2) To force the approximate codes to associate with label information and enforce the approximate codes to satisfy the block-diagonal structures as much as possible, we include a block-diagonal discriminative approximation term. LC-PDL also computes a projection to extract block-diagonal features to approximate the coefficients of samples.

(3) To minimize the classification error jointly, LC-PDL trains a robust l2,1-norm based classifier over the approximate block-diagonal codes for accurate label predictions.

2 DPL Revisited

Suppose that [ ] 1 , , n N c X X X × = ∈   is the training set, where c is the total number of classes, n is the original dimension and N is the number of training samples. 1 , i i n N i i iN X x x ×   = ∈     is the training subset of class i, where Ni is the number of the training samples in class i. DPL aims at learning a synthesis class-specific dictionary [ ] 1 , n K c D D D × = ∈   and an analysis dictionary [ ] 1 ; K n c P P P × = ∈   jointly by solving

where i X is the complementary data matrix of l X in X, j d is the j-th atom of dictionary, K is the number of atoms, the constraint 2 2 1 j d ≤ over j d is to avoid the trivial solution of 0 i P = and can make the method stable. By setting 0 i q PX ≈ , q i ∀ ≠ , the approximate codes PX are nearly block-diagonal. It is worth noting that when the size of training set is large, the above computation burden will be heavy consequently.

Given a new test sample new x , the recent DPL algorithm predicts its class label by

That is, DPL classifies each new data new x by minimizing the residual between the testing sample and its reconstructed approximation by applying the synthesis sub-dictionary and the analysis sub-dictionary within each class, while it cannot obtain an explicit classifier for data classification.

3 Scalable Block-Diagonal Locality-Constrained Projective Dictionary Learning (LC-PDL)

3.1 The Objective Function

RDDL mainly improves the scalability of DL, and forces the approximate codes to deliver block-diagonal structures. To formulate the problem, we consider three sub-problems:

Scalable Structured Block-Diagonal Projective DL

LC-PDL aims to learn the coding coefficients and dictionary of each class separately, so we first incorporate a structured synthesis dictionary [ ] 1 = , n K c D D D × ∈   . To gain a projection P for extracting the codes from data, we define the scalable projective dictionary learning process as follows:

where i X is the set of training samples of class i, , 0 j l A ≥ is a nonnegative constraint, i N is the number of training samples in the class i and k is the number of the atoms in each class. [ ] 1 , K K c Q Q Q × = ∈   is a discriminative transformation matrix and K k i Q × ∈ corresponds to the sub-dictionary in the class i. Denote the m-th row of i Q by m i Q , if m i Q and the dictionary item j d share the same label, the elements in j i Q are all ones; otherwise, =0 j i Q . For example, assuming that [ ] 1 6 = , D D D  and [ ] 1 6 = , X x x  , where 1 x and 2 x are from class 1, 3 x and 4 x are from class 2, 5 x and 6 x are from class 3, each sub-dictionary [ ] 2 1 2 = , i i i D d d - , then Q can be defined as the euqation in (4).

Term 2 i i i F PX Q A - is discriminative approximation error, which enforces the approximate coding coefficients i PX to approximate the block-diagonal coefficients i i Q A . By forcing the approximate coding coefficients to associate with label information, one can enforce PX to be block-diagonal.

Locality Preservation of Atoms for Codes

Encoding the pairwise similarities in DL process is important, as the locality constraint can ensure the learnt representation of samples to deliver similar structures. Following [Li et al., 2015], we define an adjacent matrix M over dictionary as

where δ is kernel width and ( ) dν  is the k-nearest neighbor set of atom dν . Then, a graph Laplacian L can be defined as

where d M is a diagonal matrix satisfying ( ) , 1 k d m l mm l M M = =∑ . Since the profiles and atoms have one-to-one correspondence relationship, we can define the locality constraint as

where i L is the graph Laplacian matrix of atoms in class i,  j a and  u a are the j-th row and u-th row of i A , respectively. This locality constraint can ensure that the similar profiles encourage the corresponding atoms to be similar.

Modeling a Robust Discriminartive Classifier by BlockDiagonal Representation

We introduce a variable label vector for each data i x as i h = [ ] 0, 1, 0 c ∈    , where the position of nonzero value indicates the label of i x . We also assume that its label vector can be approximated by its embedded coefficient i Px using a linear classifier c K W × ∈ , i i h WPx ≈ . Suppose that [ ] 1 , c m m H h h × = ∈   are the class labels of training signals, we use the following l2,1-norm regularized problem for robust classifier training:

where the l2,1-norm regularization term 2,1 W Τ can encourage the learned classifier W to be sparse in rows [Zhang et al., 2015] so that robust and discriminative soft labels can be learnt to improve the data representation and classification.

According to the above definitions in Eqs.(3), (7) and (8), we can obtain the final objective function of LC-PDL as

where 0 α ≥ and 0 β ≥ are tuning parameters. To illustrate that the learnt coding coefficients of training and test samples are block-diagonal, we prepare a simulation using Yale face database (at http://vision.csd.edu/content/yale-face-database). We firstly exhibit the coding coefficients A using dictionary learning in Figure 1(a), and illustrate the approximate coding coefficients PX by direct embedding with the projection P in Figure 1 (b), from which we see that the learned coefficients matrix A and approximate coefficients matrix PX are all nearly block- diagonal, implying that the dictionary would be potentially overcomplete and the classification result over approximate coefficients PX would be more accurate.

3.2 Optimization

We first initialize D, P and W to be random matrices with unit F-norm. The minimization can be alternated among the steps:

Fix D and P, Optimize A

By removing the terms that are irrelevant to A, we can obtain the following sub-problem:

(11)

where ( ) ( ) ( ) +1 +1 max , 0 t t A A = means that replacing the negative entries with 0 to ensure the nonnegative property of ( ) +1 t A .

Fix A and W, Optimize P

By removing terms that are irrelevant to P , we can obtain the following sub-problem:

We consider to solve the following approximate problem: ( ) ( ) 1 argmin g , t P P P where + =

By setting ( ) g / 0 P P ∂ ∂ = , we can update projection ( ) +1 t P as

Fix P, Optimize W and Λ

We update W and Λ alternately. According to property of the l2,1-norm [Hou et al., 2014; Zhang et al., 2015], that is, ( ) 2,1 2 W tr W W Τ Τ = Λ , where Λ is a diagonal matrix with the entries being 2 1/ 2 mm m w Λ = and m w is the m-th column of W. Then, we can update W and Λby

when each 0 m w ≠ . We first fix Λ to update W. By setting ( ) , / 0 W W ∂℘ Λ ∂ = , we can easily update ( ) 1 t W + as

Then, we can use W to update Λ . According to [Zhang et al., 2015], we can update the diagonal elements of ( ) +1 t Λ as

where ( ) 1 t m w + is the m-th column of ( ) 1 t W + . Λ is initialized to be an identity matrix similarly as [Hou et al., 2014; Zhang et al., 2015] that shows that this choice generally works well.

Fix A, Optimize D

The optimization process of updating D can be formulated as

where a variable S is involved [Gu et al., 2014]. The optimal solution of Eq.(18) can be obtained by ADMM algorithm:

Then we can update the graph Laplacian matrix ( ) 1 t i L + by (8) and (9). We summarize the LC-PDL in Algorithm 1.

3.3 Convergence Analysis and Complexity

The objective function of LC-PDL in Eq.(9) is a bi-convex problem for ( ) ( ) { } , , , , , D P W A L Λ . By fixing D, P and Λ , the function is convex for W, L and A. Similarly, by fixing W, L and A, the resulted function is also convex for D, P and Λ , since L completely depends on D. Thus, the proposed optimization of LC-PDL is actually an alternate convex search (ACS) method [Gorski et al., 2007]. Note that the convergence of this kind of problem has been well studied in [Gu et al., 2014]. As we can achieve the optimal solutions of updating variables A, W, P, D, L and Λ , our objective function has a general lower bound and the algorithm can be ensured to converge to a stationary point. It is empirically found that LC-PDL converges rapidly. Figure 2 shows the convergence

Algorithm 1 Scalable Locality-Constrained Projective DL

Input: Training data matrix X and class label matrix H Parameters: Parameters τ ,α , β , and dictionary size K Output: D, A, P, W.

• 1: Initialize D (0) and P (0) as random matrices with unit F-norm, and initialize the diagonal matrix I Λ = ; t=0;
• 2: while not converge do
• 3: 1 t t ← + ;
• 4: Update the coding coefficients matrix ( ) 1 t A + by (11);
• 5: Update the projection matrix ( ) 1 t P + by (14);
• 6: Update the linear multi-class classifier ( ) 1 t W + by (16);
• 7: Update the diagonal matrix ( ) 1 t + Λ by (17);
• 8: Update the dictionary ( ) 1 t D + by solving (18);
• 9: end while
• 10: return solution

curve of LC-PDL on MIT CBCL database [Weyrauch et al., 2004]. We can easily find that the objective function value of our LC-PDL method drops quickly and converges to a small value after 10 iterations in most cases.

In the training phase of LC-PDL, A, W, P, D, L and Λ are updated alternately. Note that we update A, D, and L class by class. The complexity of updating the variables i A , i D and i L is ( ) 2 3 i O k n k KnN + + , ( ) ( ) 3 2 2 O T cnN c c n n c + + + and ( ) 3 O k in each iteration, respectively, where T is the iteration number in ADMM algorithm for updating D. The time complexity of updating W, P and Λ are ( ) 3 O cnN cKn KnN K + + + , ( 2 O K c + ) 3 K KnN KcN + + and ( ) 2 O n N in each iteration, respectively.

3.4 Classification Approach

After the projection P* and classifier W* are obtained by our LC-PDL, we can perform classification to include new test data. Given a new test sample new x , we first embed it onto the projection P* in the form of * new P x to approximate its coding coefficient. Then, we can embed the approximate coding coefficient onto the linear classifier W* further in the form of * * new W P x , i.e., the soft label vector new f can be obtained as

where the position corresponding to biggest element in label vector new f determines the class assignment of new x . That is, the hard label of new x is assigned as ( ) argmax i c new i f ≤ , where ( ) new i f is the i-th entry of estimated soft label vector new f .

4 Experimental Results and Analysis

The performance of our LC-PDL is compared with several closely related SRC [Wright et al., 2009], K-SVD [Aharon et al., 2006], D-KSVD [Zhang and Li, 2010], LLC [Wang et al., 2010], LC-KSVD [Jiang et al., 2013], FDDL [Yang et al.,

2014], DPL [Gu et al., 2014] and LCLE-DL [Li et al., 2015]. We perform all the simulations on a PC with Intel (R) Core (TM) i3-4130 CPU @ 3.4 GHz 8G.

4.1 Image Classification

We provide the experimental results on image classification.

MIT CBCL Face Database [Weyrauch et al., 2004]

MIT CBCL database has 324 images per person (3,240 face images totally) rendered from 3D head models. Following the common evaluation procedures, the second face set is tested. All the face images are resized into 32×32 pixels for efficiency. Note that we first normalize each sample to have unit l2-norm for simulations. We randomly select 4 images per person for training, while test on the rest. The number of dictionary atoms is simply set as the number of training data. Parameters =0.01, τ =0.01 α and =0.1 β is used in our LC-PDL.

AR Face Database [Martinez and Benavente, 1998]

The AR face database consists of over 4,000 color images of 126 people. Each person has 26 face images taken during two sessions. By following the standard evaluation procedures in [Jiang et al., 2013], the sample set that contains 2,600 images of 50 male subjects and 50 female subjects is selected for the simulations. Each face image of 165×120 pixels is projected onto a 540-dimensional vector with a generated matrix from a zero-mean normal distribution. By following [Jiang et al., 2013], we also randomly choose 20 images per person for training and the rest for testing. The dictionary contains 500 items, corresponding to an average of 5 items each category. =0.01, τ =0.01 α , =0.1 β is set in our LC-PDL.

Caltech101 Fatabase[Perona et al., 2004]

The Caltech101 database contains 9144 images, consisting of

101 object classes and 1 background class. The number of images in each class varies from 31 to 800. By following the common evaluation procedure, the standard bag-of-words (BOW) plus spatial pyramid matching (SPM) [Lazebnik et al., 2006] approach is applied for feature extraction. Dense SIFT descriptors are extracted on the grid sizes of 1 1 × , 2 2 × and 4 4 × to obtain the SPM features. We then use the vector quantization based coding way to extract mid-level features and use the standard max pooling method to obtain the highdimensional pooled features. At last, the dimension of pooled features is reduced to 3,000 by PCA. In this experiment, we randomly select 5 images from each category for training and use the rest for testing. The dictionary contains 204 items, corresponding to an average of 2 items each category. The parameters =0.01, τ =0.1 α and =0.1 β are set for LC-PDL.

Caltech256 Database [Griffin et al., 2007]

We evaluate each method by using Caltech256 database that contains 30,607 images of 257 categories, such as bear, brain, tower, car, etc. The number of images in each class is at least 80. Each object image has been resized into 64 64 × due to the consideration of computational efficiency. In this study, we perform dictionary learning using discriminant features, i.e., we use the Linear Discriminant Analysis (LDA) [Fukunaga, 1990] to reduce the dimension. For LDA, the eign-problem is solved by SVD, the regularization parameter is set to 0.1. Finally, the dimension of each image is reduced to 256. We randomly select 10 images per category for training and test on the rest. The dictionary size is set as its maximum for each algorithm. =0.001, τ =0.1 α and =1 4 e β - are set in LC-PDL.

We repeat the experiments 10 times with different random spits of training and test images and average the results over different runs. All the classification results are illustrated in Table 1. We can find that our presented LC-PDL algorithm can deliver better accuracies than its competitors on all the used databases under the same setting.

4.2 Image Classification Against Noisy Databases

We evaluate the robustness of our algorithm in this section. Technically, some numerical results have been provided to illustrate the robustness of our algorithm for handing the face images with noise. The MIT CBCL database is involved in this study, and the same setting as Subsection 4.1 is also used here. Random Gaussian noise under different variance Var is manually added to each image. We then employ the noisy databases for training and testing. We illustrate some noisy face images by setting Var=200, 400, 600, 800 and 1000, respectively. The experimental results are shown in Figure 3. From the classification results, we can easily find that the increasing of Var clearly decreases the performance of each method. Since the noise has been added to each image, some important information is lost (see Figure 3) and thus the recognition rates are decreased. We note that our algorithm delivers higher accuracies than others in most cases and the descending rate of our method is also comparable to the other baselines. The main reason is that a robust l2,1-norm is used on the linear classifier, so that discriminative features can be obtained for more accurate label prediction results [Hou et al., 2014; Zhang et al., 2015].

4.3 Comparison of Computational Time

We use the MIT CBCL and Caltech256 databases to evaluate the runung time performance of each method in this study, and use the same setting as Subsection 4.1. That is, we use 40 and 2,570 images as the training set and use 3,200 and 28,037 images as the test set for MIT and Caltech256, respectively. The computational time (including the training and testing time) of each method is shown in Figure 4. We can find that when the size of training set is small, all evaluated methods spend less time in training on MIT. But for a large testing set, the testing time of KSVD, DKVD and LC-KSVD2 is far more than those of DPL and our LC-PDL, which is due to the fact that KSVD, DKSVD and LC-KSVD have involved extra time-consuming sparse reconstruction process for each test data to obtain the sparse codes for classification. From Figure 4b, we can observe that when the training set contains a large number of images, both the needed training time and testing time of KSVD, DKSVD, LC-KSVD2 and DPL are more than our LC-PDL, which is due to the fact that KSVD, DKSVD and LC-KSVD employ the time-consuming l0 or l1-norm sparsity constraint to obtain the codes, and DPL uses a large complementarty data matrix for the optimization, while our proposed LC-PDL uses a new discriminative approximation error term to avoid the above problems and it can force the approximate coding coefficients to be block-diagonal.

4.4 Parameter Analysis

We analyze the parameter sensitivity of our algorithm in this study. Since parameter selection still remains an open issue, we also use a heuristic approach to select the most important parameters (τ , α , β ) for our model. Specifically, we fix one of the parameters and explore the effects of other two on the performance employing grid search. In this study, the AR face dataset is utilized. 20 face images of each person are randomly chosen as input signals. The rest is used for testing. The trained dictionary contains 500 items. For each pair of parameters, we average the results based on 10 random splits of training and testing images with varied parameters from { } 6 4 6 10 ,10 , 10 - -  . We show the parameter selection results in Figure 5. LC-PDL works well in a wide range of parameters α and β , which means our LC-PDL model is insensitive to the parameters α and β by delivering stable performances. It is also noted that that a larger τ than 10 -2 tend to decrease the recognition result, i.e., a small τ can be used.

5 Concluding Remarks

We proposed a new structured and scalable discriminative dictionary learning framework that integrates the dictionary learning, block-diagonal representation and classification to a unified model. To make the learnt dictionary discriminative for representation, we proposed an efficient way to consider local and label information of dictionary atoms to ensure the block-diagonal structure of coeffcients without using costly l0/l1-norm sparsity. We also incorporate a new discriminative approximation term to compute a projection to approximate the codes by extracting block-diagonal features of data, and train a classifier over approximate codes. This classification process is efficient since it avoids the extra time-consuming sparse reconstruction process with well-trained dictionary for each new data, suffered in many existing methods. LC-PDL also reduces the computation cost in the training phase by avoiding the invovlvement of the complementary data matrix when learning the sub-dictionary over each class.

We have examined the effectiveness of our algorithm on several widely-used image databases. The investigated cases demonstrate superior performances of our proposed method in classification and efficiency, by comparing with several related dictionary learning methods. In future, extending our method to the semi-supervised scenario needs investigation, since the number of labeled data is typically small in practice.

Acknowledgments

The authors acknowledge support of the National Natural Science Foundation of China (Nos. 61672365, 61732008, 61725203, 61871444), and the Fundamental Research Funds for the Central Universities of China (JZ2019HGPA0102).

α

Figure 5: Parameter sensitivity analysis of our LC-PDL under different parameters on AR dataset. Left: the effects of tuningα and β by fixing =0.01 τ ; Middle: the effects of tuningα and τ by fixing =0.1 β ; Right: the effects of tuning β andτ by fixing =0.1 α .