Locality Constrained Analysis Dictionary Learning via K-SVD Algorithm

Recent years, analysis dictionary learning (ADL) and its applications for classification have been well developed, due to its flexible projective ability and low classification complexity. With the learned analysis dictionary, test samples can be transformed into a sparse subspace for classification efficiently. However, the underling locality of sample data has rarely been explored in analysis dictionary to enhance the discriminative capability of the classifier. In this paper, we propose a novel locality constrained analysis dictionary learning model with a synthesis K-SVD algorithm (SK-LADL). It considers the intrinsic geometric properties by imposing graph regularization to uncover the geometric structure for the image data. Through the learned analysis dictionary, we transform the image to a new and compact space where the manifold assumption can be further guaranteed. thus, the local geometrical structure of images can be preserved in sparse representation coefficients. Moreover, the SK-LADL model is iteratively solved by the synthesis K-SVD and gradient technique. Experimental results on image classification validate the performance superiority of our SK-LADL model.


Introduction
Sparse representation which encodes the signals or images using only a few active coefficients, has been successfully applied to many areas across signal processing and pattern recognition. Signals can be represented as a linear combination of a relatively small number of atoms in an over-complete dictionary. Sparse representation models can be classified into two categories by the learning method, synthesis dictionary learning (SDL) and analysis dictionary learning (ADL) [1,8]. A typical SDL model expects to learn the over-completed dictionary by minimizing the reconstruction errors such that it can linearly represent the original signals. Instead of learning an over-complete representation dictionary in SDL, the ADL model mainly focuses on learning a transformation matrix, and constructing sparse analyzed vectors. The ADL model has aroused much attention as it has a more intuitive illustration for the role of analysis atoms and high efficiency.
The traditional SDL model views the signal reconstruction problem as a pure approximation task, which may overlook signal intrinsic attributes, such as signal structure and density. To overcome this issue, several sparse coding models incorporating the geometrical structures of the image space have been proposed. They are based on the locally invariant idea, which assumes that two close points in the original space are likely to have similar encodings. Thus, additional regularizers are incorporated in order to satisfy specific requirements in various application scenarios. For example, graph regularized sparse coding based on nonlinear manifold learning is proposed for image classing and clustering applications [3,4,11,14]. Motivated by recent progress in sparse representation, we combine the ADL model with manifold learning, called locality constrained ADL with a synthesis K-SVD solver (SK-LADL). The flowchart of our proposed method for classification is illustrated in Fig. 1. The novel strategy incorporates the graph regularizer to emphasize the correlations between neighbors of training data, which could enhance the discriminative ability of the analysis dictionary. The rest of this paper is organized as follows. The basic dictionary learning framework is presented in Section 2. The locality constrained analysis dictionary learning model is presented in Section 3. The K-SVD algorithm is introduced in Section 4. The classification methodology adopted in our model is reviewed in Section 5. Experimental results on image classification are presented in Section 6. Relevant conclusions are finally given in Section 7.

Synthesis Dictionary Learning
Given signals Y = [y 1 , y 2 , · · · , y n ] ∈ R m×n , let D = [d 1 , d 2 , · · · , d k ] ∈ R m×k be a synthesis dictionary with a serials of atom d i , and X = [x 1 , x 2 , · · · , x n ] ∈ R k×n be the sparse coefficient matrix. The main idea of synthesis dictionary learning (SDL) is to approximately reconstruct the original signals Y by the combination of dictionary atoms d i (1 ≤ i ≤ k) with respective weight factors or coefficients X. The sparse optimization problem of SDL can be formulated as follows.
where Y − DX 2 F is the reconstruction error term and λ is a positive weight coefficient [1].
Sparse representation of the above SDL model can be classified in two basic tasks, i.e., sparse approximation and dictionary learning. The task of sparse approximation is to find a sparse solution to an underdetermined linear system. Some algorithms, such as matching pursuit (MP), basis pursuit (BP) and shrinkage method, have been well developed. On the other hand, dictionary learning is dedicated to search an optimal signal space to support the attribution of sparse vector under a certain measure. There exist a variety of numerical algorithms presented to achieve this objective, e.g., the method of optimal directions (MOD), K-means singular value decomposition (K-SVD) and recursive least squares (RLS).
The sparse analysis dictionary learning (ADL) model aims to learn a projective matrix (i.e., analysis dictionary) Ω ∈ R k×m with k > m to implement the approximately sparse representation of the signal y ∈ R m in transformed domain [7,8]. Specifically, it assumes that the product of Ω and y is sparse, i.e., x = Ωy with x i 0 = k − l, where 0 ≤ l ≤ k is the number of zeros in x ∈ R k . The sparse optimization problem can be formulated as follows. min where the representation error term X − ΩY 2 F shows the disparity between image representations in the transformed space and the coefficients with target sparsity level. The optimization problem in equation (2) above can be rewritten in the vector form as If the signal y i is known, its analysis representation with respect to a given dictionary can be obtained via multiplying by Ω. However, when the observed signal is contaminated by noise, the clean signal has to be estimated first in order to get its analysis representation, which leads to the analysis pursuit problem. Some algorithms like backward-greedy (BG), optimized-backward-greedy (OBG), and greedy analysis pursuit (GAP) have been proposed to address this problem [8].
The computational complexity of the basic ADL model is very high, and some recent work has relax the l 0 -norm in equation (3) to l 1 -norm or thresholding function [10].

Locality Constrained Analysis Model
The local geometric structure such as texture and contour information can be added to the sparse representation problem to upgrade the accuracy of signals approximation. Locality is more essential than sparsity, since locality leads to sparsity but not necessary vice versa [15]. The manifold learning theory can be used to quantify intrinsic geometric locality structure information. Many previous works have demonstrated that local structure embedded in high-dimensional vector space is very important to characterize both the intrinsic structure and discriminative structure of images [2]. Moreover, since the data is more likely to reside on a low-dimensional sub-manifold embedded in the high-dimensional ambient space, the geometrical information of the data is important for discrimination [4,6,14]. Therefore, by preserving the locality characteristics of the training samples, the discriminative ability of the learned dictionary can be improved. Motivated by previous works, a natural assumption here is that if two samples y i and y j are close to each other in the intrinsic geometric structure of the data distribution, the sparse representation vectors x i and x j over dictionary Ω , should be also close to each other. By use of techniques from Laplacian eigenmap method, we employ the graph Laplacian to build the local manifold structure. Specifically, we construct a supervised nearest neighbor graph G = {Y, W } with N vertices, in which each vertex denotes a data point, and the similarity matrix W over training samples is defined as where δ is kernel width and N(y i ) is the k-nearest neighbors of sample y i . To map the supervised nearest neighbor graph G to the sparse representation matrix X we minimize the following graph Laplacian criterion where L = B − W is called as graph Laplacian matrix, B is a diagonal weight matrix with ith diagonal entry is B ii = W ji . Thus, with the regularizer T r(XLX T ), the corresponding representations of any two points y i and y j are expected to maintain the same local structure of them. Then the sparse representation problem can be formulated as where α is weight coefficient, L is a weight matrix depended on the chosen manifold. As the Laplacian is symmetric and positive semidefinite, the objective (6) is a convex optimization problem. We rewrite the Laplacian regularizer T r(XLX T ) in equation (6) to the vector form as The optimization problem in equation (6) above can be rewritten in the vector form as When the dictionary Ω and all the other vectors {x k } k =i are fixed, we obtain the following optimization problem After some manipulations, problem (9) can be further cast as Then, merging two l 2 -norm terms in (10) yields the final SK-LADL model as where I is an identity matrix and R is initialized as an identity matrix, each element of p i is defined by

Solving the Problem
In this section, we adopt an alternative strategy to solve the SK-LADL model. The synthesis K-SVD and gradient technique are incorporated into the optimization procedure. The iterative optimization algorithm contains the following two steps: Update {X} Fixing the dictionary Ω, the solutions for X in the present iteration can be obtained by utilizing the synthesis K-SVD. Denote the two combined matrices in the parentheses of problem (11) as In the original K-SVD algorithm, the matrix Q new is column-wise l 2 normalized. The optimization problem (11) is equivalent to the following problem: The optimization problem in (15) can be solved by the K-SVD method, with entrance parameters being y new , Q new and T 0 . Let x k R be the corresponding coefficients of the kth column of Q new , and denoted as q k . Let E k = Y new − j =k q j x j R , then discard the zero entries in x k R and E k , with corresponding results marked asx k R andẼ k respectively. We optimize the following problem to obtain q k and x k R .
q k ,x k R = arg min DecomposingẼ k by K-SVD method, we haveẼ k = U ΣV T . Letx k R = Σ (1, 1) V (:, 1). After that, the nonzero values of x k R are replaced byx k R . Then the dictionary R t in Q t new can be used for the next iterator, i.e., R t+1 = R t . And the Q t+1 new is updated accordingly with R t+1 and the Laplacian matrix L. Update {Ω} Fixing X, the solution for Ω is computed through matrix derivation, followed by normalization of the rows of Ω. We add the following regularization term into the object function. The formulation in this situation is given as After omitting the independent terms, an equivalent problem is obtained as follows. min where β is a parameter which indicates the weight of the penalty term. The role of this term lies in avoiding singularity and over-fitting issues as well as ensuring the stable solution of dictionary. Let the first derivative w.r.t. Ω be zero and we can obtain the closed-form analytical solution for the dictionary as Then we normalize rows of the dictionary, which results in better performance empirically. The above training procedure is outlined in Algorithm 1.

Algorithm 1 Algorithm for solving our proposed model
Input: Training data Y , model parameter α,β. Output: The analysis dictionary Ω.

Classification Methodology
For classification of test samples on SK-LADL model, preliminary representation coefficient x i are obtained via the operation of multiplying Ω by the testing sample y i . Keeping in view that the proposed SK-LADL method imposes sparsity on coefficients, a hard thresholding operator is used to maintain the sparse characteristic of x i . The operator reserves elements with T 0 biggest absolute values and sets the others to be zero. Then, the multivariant ridge regression model is used to obtain a linear classifier from the sparse representations X for training samples Y : min where δ is a parameter for regularizing the solution, H = [h 1 , h 2 , · · · , h n ] is the label matrix of sparse analysis representation X, and each column h i = [0, · · · , 0, 1, 0, · · · , 0] T describes the label vector of the ith sample. The optimal solution of above problem is With the optimized W * , a testing sample y i can be predicted by picking the index of the maximum element of W * x i . Then let the predictive vector h ipre = W x i . The predictive vector h ipre has a very approximate shape to the corresponding real label vector h i , with only one element obviously bigger than others. Therefore, the location of the largest element in h ipre is utilized to determine the category.

Experiment Setups
In this section, we evaluate our SK-LADL model on four public image datasets, Extended YaleB (EYaleB), AR, Scene15 and UCF50. The above databases are widely used in evaluating the performance of sparse representation-based classification methods. The features are provided by [5] and [9]. On EYaleB and AR datasets, random features are generated by the projection with a randomly generated matrix. On Scene15 datasets, features are achieved by extracting SIFT descriptors, max pooling in spatial pyramid and reducing dimensions by PCA. UCF50 is a large-scale and challenging action recognition database. It has 50 action categories and 6680 realistic human action videos collected from YouTube. AR face database contains illumination, expression, and occlusions variations. We choose a subset consisting of 2600 face images from 50 males and 50 females. We compare our model with some state-of-the-art approaches: SRC [13], K-SVD [1], D-KSVD [16], LC-KSVD [5], ADL-SVM [10] and SK-DADL [12] with the above benckmark image datasets features. For fair comparison, the experiment settings we follow are in accordance with [5] and [12]. The sparsity is set as 45 in all the methods, and the dictionary atom is set between 500 and 600 which is the integral multiple of the number of classes in different datasets. There are four parameters in SK-LADL model, i.e., α, β, δ and k, where δ = 0.01 and k = 3 are preset and the parameter α and β are tuned by 5-fold cross validation and optimized by using grid search strategy. We firstly search in the larger range of [10 −3 , 10 −2 , · · · , 10 2 , 10 3 ] for each parameter and then search a smaller grid with proper interval size determined by preliminary classification results.The best parameters we set in each database are listed in Table 1.

Results and Analyses
We repeat the experiments 5 times on different selected training and testing image features, and the mean accuracies are reported. Table 2 shows the mean classification accuracy results on different datasets. As can be seen, our method achieves notably higher accuracy than SRC, KSVD and LC-KSVD on all four databases. This is mainly due to the locality preservation achieved in our method for ADL model, which ensures that similar training samples tend to have similar coding coefficients. The SRC model that directly uses all training samples as the dictionary will introduce noise for the sparse representation. The locality constraint on representation coefficients can narrow the selection of representative analysis atoms on geometric manifold, enhance the representational ability of homogeneous samples to some extent, and this may help to overcome the above noise disadvantage. Our method also achieves favorable results compared with the two ADLbased methods. This is mainly because the ADL-SVM and SK-DADL model only utilize joint-or post-learned classifiers with analysis representation without inherit the underlining structure of training samples. Therefore, with only a simple post-learned classifier, the integration of the locality information yields attractive discrimination for SK-LADL model compared to other conventional ADL models. As for the testing efficiency, Table 3 shows the time for classifying one testing image on databases EYaleB (dictionary size = 570) and AR (dictionary size = 600). As can be seen, our method performs better than SK-DADL, due to the locality constraint on sparse coding, which could generate similar analysis representation of heterogeneous samples. The accuracies and time costs in tables can demonstrate that our SK-LADL model has huge potential in pattern classification tasks.  Fig. 2 shows the confusion matrix for our proposed SK-LADL method on Scene15 dataset. It presents proportion of images in each category classified to all categories. We can observe that most images can be classified into the right category, with some class even getting all right classification. From the figures, we can conclude that the desired effect of our proposed SK-LADL method is reached.

Conclusion
In this paper, we proposed a novel discriminative analysis dictionary learning model with locality constrained regularizer(SK-LADL), which takes into account the intrinsic geometric structure of the training samples by introducing the locality constraint term into the framework. To effectively solve the proposed objective function, an iterative algorithm based on the conventional synthesis K-SVD and gradient technique are applied to our SK-LADL model. Experimental results on four benchmark image datasets classification demonstrate the superiority of the SK-LADL method over other state-of-the-art ADL approaches. In the future, we will incorporate locality constraint on dictionary atom and coefficients, addressing the problem when both training and test images are corrupted.