# Optimizing Kernel PCA Using Sparse Representation-Based Classifier for MSTAR SAR Image Target Recognition

Authors: Chuang Lin; Binghui Wang; Xuefeng Zhao; Meng Pang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Different kernels cause various class discriminations owing to their different geometrical structures of the data in the feature space. In this paper, a method of kernel optimization by maximizing a measure of class separability in the empirical feature space with sparse representation-based classifier (SRC) is proposed to solve the problem of automatically choosing kernel functions and their parameters in kernel learning. The proposed method first adopts a so-called data-dependent kernel to generate an efficient kernel optimization algorithm. Then, a constrained optimization function using general gradient descent method is created to find combination coefficients varied with the input data. After that, optimized kernel PCA (KOPCA) is obtained via combination coefficients to extract features. Finally, the sparse representation-based classifier is used to perform pattern classification task. Experimental results on MSTAR SAR images show the effectiveness of the proposed method.


---

## Body

## 1. Introduction

Recently, kernel learning or kernel machine has aroused broad interest in pattern recognition and kernel learning areas. For classification problem based supervised kernel learning, different kernel geometrical structures give different class discriminations. However, separability of the data in the feature space could be even worse if an inappropriate kernel is chosen since the geometrical structure of the mapped data in the feature space is totally determined by the kernel matrix, so the selection of kernel influences greatly the performance of kernel learning and thus optimizing kernel can be regarded as an effective way to improve classification performance. Considering that optimized kernel parameters of kernel function cannot change the geometrical structures of kernel in the feature space [1, 2], so it cannot improve the performance of kernel learning. In this sense, Scholkopf et al. [3] proposed an empirical kernel map which maps original input data space into a subspace of the empirical feature space. Since the training data have the same geometrical structure in both the empirical feature space and the feature space, and the former is easier to access than the latter, it is easier to study the adaptability of a kernel to the input data and to improve it in the former space. Cristianini et al. [4] and Lanckrict et al. [5] have proposed methods of choosing kernel by optimizing the measure of data separation in the feature space for the first time. Cristianini et al. and Lanckrict et al., respectively, employ the alignment and margin as the measure of data separation to evaluate the adaptability of a kernel to input data. Zhang et al. proposed several variants of KPCA [6, 7] to perform fault diagnosis and nonlinear processes. Then, they utilized the improved kernel learning techniques to deal with statistical analysis of nonlinear fault detection [8], large-scale fault diagnosis processes [9], and the monitoring of dynamic processes [10].Simultaneously, sparse representation has gained great interest in pattern recognition and computer vision areas recently. Wright et al. [11] presented a sparse representation based classification method [12] and applied it to real-world face recognition problems [11, 12]. With varying expression and illumination, as well as occlusion and disguise, it was very effective and robust for face recognition.The paper is organized as follows: in Section2, we first introduce the concept of data-dependent kernel and empirical feature space. Then, we optimize the kernel in the empirical feature space by seeking the optimal combination coefficients of data-dependent kernel based on Fisher criterion. In Sections 3 and 4, the optimized kernel PCA (KOPCA) is adopted for MSATR SAR images to obtain dimensionality reduced empirical feature so as to employ sparse representation-based classifier for pattern classification. Finally, in Section 5, experiments are carried out on MSTAR SAR images to demonstrate the improvement in the performance of the data classification algorithms after using the optimized kernel and sparse representation-based classifier.


## 2. Kernel Optimization in the Empirical Feature Space

### 2.1. Data-Dependent Kernel

Since different kernels create different geometrical structures of the data in the feature space and lead to different class discriminations [13], there does not exist a kernel function that can be adaptive to all datasets in kernel learning. Therefore, data-dependent based kernel is necessary to be chosen to deal with the problem. In this paper, we employ a data-dependent kernel which is proposed by Amari and Wu [14] to be the objective kernel function to conduct kernel optimization. There is a need to explain that the data-dependent kernel is a conformal transformation to a basic kernel.Given a set ofN training samples x1,…,xN∈Rd, the data-dependent kernel is defined as follows:
(1)k(x,y)=q(x)q(y)k0(x,y),
where x,y∈Rd, k0(x,y) is a basic kernel such as a polynomial kernel or Gaussian kernel. q(·) is a positive real valued factor function and different q(·) make the data-dependent kernel different properties; Amari and Wu [14] expand the spatial resolution in the margin of a SVM by
(2)q(x)=∑i∈SVαik1(x,ai),
where k1(x,ai)=exp(-γ∥x-ai∥),  ai∈Rd is the ith support vector, and SV is a set of support vector. The set {a∣a=[a1,a2,…,an]} called the “empirical cores,” can be determined according to the distribution of the training data. γ is a free parameter. αi{i=0,1,…,n}  are the positive combination coefficients which are considered as contribution weights corresponding to the ai. Meanwhile, the data-dependent kernel is a kernel function as it satisfies the Mercer condition [3].LetK and K0 be the Kernel Matrices of k(x,y) and k0(x,y), respectively. Thus, it is easy to see that
(3)K=[q(xi)q(xj)k0(xi,xj)]N×N=QK0Q,
where K=[k(xi,xj)]N×N,  K0=[k0(xi,xj)]N×N and Q is a diagonal matrix with elements {q(x1),q(x2),…,q(xN)}.We denote vectors[q(x1),q(x2),…,q(xN)]T and [α0,α1,…,αn]T as q and α, respectively. Then, we have
(4)q=[1k1(x1,a1)⋯k1(x1,an)1k1(x2,a1)⋯k1(x2,an)⋮⋮⋱⋮1k1(xN,a1)⋯k1(xN,an)][α0α1⋮αn]=K1α.


### 2.2. Empirical Feature Space

The different kernels cause various class discriminations owing to their different geometrical structures of the data in the feature space. It is often not so convenient or easy to compute in feature space. Hence, the concept of empirical feature space is introduced.Letxi{i=1,2,…,N} be a d-dim training dataset and XT=[x1,x2,…,xN].  K=[k(xi,xj)]N×N denotes the kernel matrix with rank r. Since K is a symmetric positive semidefinite matrix, it can be decomposed as
(5)KN×N=PN×rΛr×rPr×NT,
where Λ is a diagonal matrix with r positive eigenvalues of K in descending order, and P contains r eigenvectors corresponding to the positive eigenvalues.On the basis of above, we can define the map from input data space toRr Euclidean space and gain the so-called empirical kernel map Φr defined in [3], that is,
(6)Φr:X→Rr,x↦Λ-1/2PT(k(x,x1),k(x,x2),…,k(x,xN))T.The embedding spaceΦr(X)⊂Rr is called empirical feature space.We can prove that the training data has the same geometric structure in both the empirical feature space and feature space. LetY=KPΛ-1/2, then the dot product matrix  {Φr(xi)} in the empirical feature space can be calculated as
(7)YYT=KPΛ-1/2Λ-1/2PTKT=K.
Notice that KT=K, K=[Φ(xi)·Φ(xj)]N×N, and the result of YYT is exactly the dot product matrix of {Φ(xi)} in the feature space; therefore, we say that the empirical feature space preserves the geometric structure in the feature space.


### 2.3. Fisher Criterion Based Kernel Optimization

As illustrated in Section2.2, the training data has the same geometric structure in both the empirical feature space and feature space and it is easier to access the empirical feature space than the feature space, so it is better to measure class separability in the empirical feature space. In this paper, we choose the acquainted Fisher criteria to measure class separability:
(8)J=trSbtrSw,
where Sb is the between-class scatter matrix, Sw is the within-class scatter matrix, and tr is the trace of given matrix. J is Fisher criteria to measure the class separability. Notice that J measures the class separability in the feature space and J is independent of the projections in the common projection subspace, so it is a satisfying choice to be the task of kernel optimization.Up to now, the kernel optimization problem is transformed to maximize Fisher scalarJ. Let the number of each class i(i=1,2,…,C) be Ni, that is, class i has Ni training samples and N denotes the number of all training samples. What is more, let mi,  m0 denote the center of each training samples in class i(i=1,2,…,C) and the center of all training samples, respectively, that is, mi=(1/Ni)∑j=1Niyj,  m0=(1/N)∑k=1Nyk and yi(i=1,2,…,N) be the images of the training samples in the empirical feature space, that is, yi=Φr(xi). Then, we can define
(9)trSb=1N∑i=1CNi(mi-m0)T(mi-m0),trSw=1N∑i=1C∑j=1Ni(yij-mi)T(yij-mi),
where yij means the jth training sample in the ith class.For the convenience of calculation and representation, we rewrite the kernel matrixK as
(10)K=[K11K12…K1CK21K22…K2C⋮⋮⋱⋮KC1KC2…KCC],
where Kij(i=1,2,…,C;j=1,2,…,C) represent the submatrices of K and the size of Kij is Ni×Nj.Let the following matricesB and W be called “between-class” and “within-class” kernel scatter matrices, respectively,
(11)B=[1N1K110⋯001N2K22⋯0⋮⋮⋱⋮00⋯1NCKCC]-1N[K11K12⋯K1CK21K22⋯K2C⋮⋮⋱⋮KC1KC2⋯KCC],W=diag(k11,k22,…,kNN)-[1N1K110⋯001N2K22⋯0⋮⋮⋱⋮00⋯1NCKCC].We can also employB0 and W0 to denote “between-class” and “within-class” kernel scatter matrices corresponding to the basic kernel K0.Now we establish the relation between Fisher scalarJ and the proposed kernel scatter matrices. Let 1N be the N-dim vector whose elements are equal to 1. Then we can get
(12)J=qTB0qqTW0q.
The proof is given in the appendix.To maximizeJ, we adopt the general gradient method and use formula (4). Define
(13)J1=qTB0q=(K1α)TB0K1α=αTK1TB0K1α,J2=qTW0q=(K1α)TW0K1α=αTK1TW0K1α.Then,(14)∂J1∂α=2K1TB0K1α,∂J2∂α=2K1TW0K1α.
Thus,
(15)∂J∂α=∂(J1/J2)∂α=(∂J1/∂α)J2-J1(∂J2/∂α)J22=2J22(K1TB0K1J2-K1TW0K1J1)α=2J2(K1TB0K1-K1TW0K1J)α.
Denote M0=K1TB0K1 and N0=K1TW0K1, maximize J is equivalent to ∂J/∂α=0, that is,
(16)M0α=N0Jα.Considering the fact that it is almost impossible to makeW0 invertible because of the limited amount of training samples in real-world applications, the general gradient descent method is adopted to get an approximate value of the optimal α. The updating equation to maximize J is defined as follows:
(17)α(n+1)=α(n)+η(1J2M0-JJ2N0)α(n).To guarantee the convergence of formula (17), η is defined as the function of iterations, that is,
(18)η(q)=η0(1-qQ),
where η0 is a predefined initial value, Q denotes total number of iterations, and q represents the current iteration number.After we calculate the combination coefficients ofα, then we can get q, as q=K1α, and thus, the optimizing kernel or data-dependent kernel, K, is easy to achieve.


## 2.1. Data-Dependent Kernel

Since different kernels create different geometrical structures of the data in the feature space and lead to different class discriminations [13], there does not exist a kernel function that can be adaptive to all datasets in kernel learning. Therefore, data-dependent based kernel is necessary to be chosen to deal with the problem. In this paper, we employ a data-dependent kernel which is proposed by Amari and Wu [14] to be the objective kernel function to conduct kernel optimization. There is a need to explain that the data-dependent kernel is a conformal transformation to a basic kernel.Given a set ofN training samples x1,…,xN∈Rd, the data-dependent kernel is defined as follows:
(1)k(x,y)=q(x)q(y)k0(x,y),
where x,y∈Rd, k0(x,y) is a basic kernel such as a polynomial kernel or Gaussian kernel. q(·) is a positive real valued factor function and different q(·) make the data-dependent kernel different properties; Amari and Wu [14] expand the spatial resolution in the margin of a SVM by
(2)q(x)=∑i∈SVαik1(x,ai),
where k1(x,ai)=exp(-γ∥x-ai∥),  ai∈Rd is the ith support vector, and SV is a set of support vector. The set {a∣a=[a1,a2,…,an]} called the “empirical cores,” can be determined according to the distribution of the training data. γ is a free parameter. αi{i=0,1,…,n}  are the positive combination coefficients which are considered as contribution weights corresponding to the ai. Meanwhile, the data-dependent kernel is a kernel function as it satisfies the Mercer condition [3].LetK and K0 be the Kernel Matrices of k(x,y) and k0(x,y), respectively. Thus, it is easy to see that
(3)K=[q(xi)q(xj)k0(xi,xj)]N×N=QK0Q,
where K=[k(xi,xj)]N×N,  K0=[k0(xi,xj)]N×N and Q is a diagonal matrix with elements {q(x1),q(x2),…,q(xN)}.We denote vectors[q(x1),q(x2),…,q(xN)]T and [α0,α1,…,αn]T as q and α, respectively. Then, we have
(4)q=[1k1(x1,a1)⋯k1(x1,an)1k1(x2,a1)⋯k1(x2,an)⋮⋮⋱⋮1k1(xN,a1)⋯k1(xN,an)][α0α1⋮αn]=K1α.


## 2.2. Empirical Feature Space

The different kernels cause various class discriminations owing to their different geometrical structures of the data in the feature space. It is often not so convenient or easy to compute in feature space. Hence, the concept of empirical feature space is introduced.Letxi{i=1,2,…,N} be a d-dim training dataset and XT=[x1,x2,…,xN].  K=[k(xi,xj)]N×N denotes the kernel matrix with rank r. Since K is a symmetric positive semidefinite matrix, it can be decomposed as
(5)KN×N=PN×rΛr×rPr×NT,
where Λ is a diagonal matrix with r positive eigenvalues of K in descending order, and P contains r eigenvectors corresponding to the positive eigenvalues.On the basis of above, we can define the map from input data space toRr Euclidean space and gain the so-called empirical kernel map Φr defined in [3], that is,
(6)Φr:X→Rr,x↦Λ-1/2PT(k(x,x1),k(x,x2),…,k(x,xN))T.The embedding spaceΦr(X)⊂Rr is called empirical feature space.We can prove that the training data has the same geometric structure in both the empirical feature space and feature space. LetY=KPΛ-1/2, then the dot product matrix  {Φr(xi)} in the empirical feature space can be calculated as
(7)YYT=KPΛ-1/2Λ-1/2PTKT=K.
Notice that KT=K, K=[Φ(xi)·Φ(xj)]N×N, and the result of YYT is exactly the dot product matrix of {Φ(xi)} in the feature space; therefore, we say that the empirical feature space preserves the geometric structure in the feature space.


## 2.3. Fisher Criterion Based Kernel Optimization

As illustrated in Section2.2, the training data has the same geometric structure in both the empirical feature space and feature space and it is easier to access the empirical feature space than the feature space, so it is better to measure class separability in the empirical feature space. In this paper, we choose the acquainted Fisher criteria to measure class separability:
(8)J=trSbtrSw,
where Sb is the between-class scatter matrix, Sw is the within-class scatter matrix, and tr is the trace of given matrix. J is Fisher criteria to measure the class separability. Notice that J measures the class separability in the feature space and J is independent of the projections in the common projection subspace, so it is a satisfying choice to be the task of kernel optimization.Up to now, the kernel optimization problem is transformed to maximize Fisher scalarJ. Let the number of each class i(i=1,2,…,C) be Ni, that is, class i has Ni training samples and N denotes the number of all training samples. What is more, let mi,  m0 denote the center of each training samples in class i(i=1,2,…,C) and the center of all training samples, respectively, that is, mi=(1/Ni)∑j=1Niyj,  m0=(1/N)∑k=1Nyk and yi(i=1,2,…,N) be the images of the training samples in the empirical feature space, that is, yi=Φr(xi). Then, we can define
(9)trSb=1N∑i=1CNi(mi-m0)T(mi-m0),trSw=1N∑i=1C∑j=1Ni(yij-mi)T(yij-mi),
where yij means the jth training sample in the ith class.For the convenience of calculation and representation, we rewrite the kernel matrixK as
(10)K=[K11K12…K1CK21K22…K2C⋮⋮⋱⋮KC1KC2…KCC],
where Kij(i=1,2,…,C;j=1,2,…,C) represent the submatrices of K and the size of Kij is Ni×Nj.Let the following matricesB and W be called “between-class” and “within-class” kernel scatter matrices, respectively,
(11)B=[1N1K110⋯001N2K22⋯0⋮⋮⋱⋮00⋯1NCKCC]-1N[K11K12⋯K1CK21K22⋯K2C⋮⋮⋱⋮KC1KC2⋯KCC],W=diag(k11,k22,…,kNN)-[1N1K110⋯001N2K22⋯0⋮⋮⋱⋮00⋯1NCKCC].We can also employB0 and W0 to denote “between-class” and “within-class” kernel scatter matrices corresponding to the basic kernel K0.Now we establish the relation between Fisher scalarJ and the proposed kernel scatter matrices. Let 1N be the N-dim vector whose elements are equal to 1. Then we can get
(12)J=qTB0qqTW0q.
The proof is given in the appendix.To maximizeJ, we adopt the general gradient method and use formula (4). Define
(13)J1=qTB0q=(K1α)TB0K1α=αTK1TB0K1α,J2=qTW0q=(K1α)TW0K1α=αTK1TW0K1α.Then,(14)∂J1∂α=2K1TB0K1α,∂J2∂α=2K1TW0K1α.
Thus,
(15)∂J∂α=∂(J1/J2)∂α=(∂J1/∂α)J2-J1(∂J2/∂α)J22=2J22(K1TB0K1J2-K1TW0K1J1)α=2J2(K1TB0K1-K1TW0K1J)α.
Denote M0=K1TB0K1 and N0=K1TW0K1, maximize J is equivalent to ∂J/∂α=0, that is,
(16)M0α=N0Jα.Considering the fact that it is almost impossible to makeW0 invertible because of the limited amount of training samples in real-world applications, the general gradient descent method is adopted to get an approximate value of the optimal α. The updating equation to maximize J is defined as follows:
(17)α(n+1)=α(n)+η(1J2M0-JJ2N0)α(n).To guarantee the convergence of formula (17), η is defined as the function of iterations, that is,
(18)η(q)=η0(1-qQ),
where η0 is a predefined initial value, Q denotes total number of iterations, and q represents the current iteration number.After we calculate the combination coefficients ofα, then we can get q, as q=K1α, and thus, the optimizing kernel or data-dependent kernel, K, is easy to achieve.


## 3. Optimizing Kernel PCA (KOPCA)

In this section, we will employ the optimized kernel function mentioned above to construct the optimizing kernel PCA and extract feature in the empirical feature space.Given a set ofN training samples x1,x2,…,xN∈Rd and an empirical feature mapping Φr, let the input data space X be mapped into the empirical feature space Rr:Φr:X→Rr,x↦Φr(x). The covariance operator on the empirical feature space Rr can be constructed by
(19)SΦr=1N∑i=1N(yi-m0)(yi-m0)T,
where yi and m0 are defined the same as above, that is, yi=Φr(xi), m0=(1/N)∑k=1Nyk. It is easy to proof that all nonzero eigenvalues of SΦr are positive, and every eigenvector β of SΦr can be linearly expanded by
(20)β=∑i=1Nθiyi.
To get these expansion coefficients, we denote β=[β1,β2,…,βm],  YT=[y1,y2,…,yN] and form an N×N Gram matrix G=YYT, whose elements are determined by optimizing kernel, that is, Gij=yiTyj=(Φr(xi),Φr(xj))=k(xi,xj). Note that the kernel matrix K=[k(xi,xj)]N×N is the same as what is defined in formula (7).CentralizeG by
(21)Gc=G-1N×G-G×1N+1N×G×1N,
where 1N is defined the same as above, that is, 1N is N-dim vector whose elements are equal to 1.Let the eigenvectors ofGc be γ1,γ2,…,γm corresponding to the m largest positive eigenvalues λ1≥λ2≥⋯≥λm. Then, the m eigenvectors of SΦr,  β1,β2,…,βm, corresponding to the m largest positive eigenvalues λ1≥λ2≥⋯≥λm, are
(22)βj=1λjYTγj.
After the projection of a mapped sample yt=Φr(xt) onto the eigenvectors β=[β1,β2,…,βm], we can obtain optimizing kernel PCA transformed feature vector z by
(23)z=βTyt.
Meanwhile, the jth optimizing kernel PCA component:
(24)zj=βjTyt=1λjγjTYyt=1λjγjT[y1Ty2T⋮yNT]yt=1λjγjT[k(x1,xt),k(x2,xt),…,k(xN,xt)]T.Up to now, the essence of optimizing kernel PCA has been revealed. That is, we first maximize a measure of class separability in the empirical feature space by virtue of Fisher criterion to form needful data-dependent kernel and then take advantage of optimizing kernel PCA to extract feature in the empirical feature space.


## 4. Sparse Representation-Based Classifier (SRC)

LetAi(i=1,2,…,C) be the matrix formed by the training samples of the ith class, that is, Ai=[xi1,xi2,…,xiNi]∈Rd×Ni. And define a new matrix A for the total training set with C classes as the concatenation of the N training samples: A=[A1,A2,…,AC]∈Rd×N.Given a test sampley from the ith class, then y can be approximately represented by the linear span of the training samples in the corresponding class, that is,
(25)y=μi1xi1+μi2xi2+⋯+μiNixiNi=∑j=1Niμijxij=Aiμi,
where μij(j=1,2,…,Ni) are the corresponding coefficients, and we denote μi=[μi1,μi2,…,μiNi]T.Then, the linear representation ofy can be rewritten in terms of A as
(26)y=Aμ,
where μ=[0,…,0,μiT,0,…,0]T∈RN is a coefficient vector whose entries are zero except those associated with the ith class.Hereto, we should take the number of row and column ofA into consideration. If the row number d is bigger than column number N, the system of equations y=Aμ is overdetermined and the correct μ can usually be found as its unique solution. Nevertheless, this is not what we need since sparse representation involves an underdetermined system of linear equations y=Aμ, where d<N as it is motivated by the following fact: given a test sample y, the representation is naturally sparse if training sample size (column number) is large enough, and if the sparser the coefficient vector μ is, the easier it will be to accurately reconstruct the identity of the test sample y [12].Consequently, it means that the dimension of feature vector (row number) must be smaller than the training sample size (column number). Considering, before we use sparse representation, we have obtained dimensionality reduced empirical feature in Section2, and just in time, it can meet requirements.The above discussion motivates us to seek the sparest solution by solving the following optimization problem:(27)(ℓ0)μ^0=argmin∥μ∥0,s.t.y=Aμ,
where ∥·∥0 denotes the ℓ0-norm, which counts the number of nonzero entries in a vector.However, solvingℓ0 optimization problem in formula (27) is NP hard and time-consuming. Recent research of spares representation and compressed sensing [15, 16] proves that if the solution μ^0 is sparse enough, the solution of the ℓ0 optimization problem is equivalent to finding the solution of the ℓ1 optimization problem:
(28)(ℓ1)μ^1=argmin∥μ∥1,s.t.y=Aμ.
This problem can be solved in polynomial time by standard linear programming algorithms [17].After obtaining the sparest solutionμ^1, we can form a sparse representation-based classifier (SRC) in the following way. For each class i(i=1,2,…,C), let δi:RN→RN be a function which selects the coefficients associated with the ith class, then δi(μ) is a vector whose only nonzero entries are the entries in μ that are associated with class i. Making use of the coefficients associated with the ith class, one can reconstruct the given test sample y as y^i=Aδi(μ^1). y^i is often called the prototype of class i with respect to the sample y. The residual between y and its prototype y^i of class i is defined as follows:
(29)ri(y)=∥y-y^i∥2=∥y-Aδi(μ^1)∥2.
Then the SRC decision rule is to minimize the residual, that is, if rk(y)=miniri(y),  y is assigned to class k. It is necessary to explain that our implementation minimizes the ℓ1-norm via the basis pursuit denoising (BPDN) algorithm for linear programming based on [17–19].


## 5. Experimental Results

In this section, experiments are designed to evaluate the performance of the proposed algorithm. The first experiment is adopted to show that the class separability is probably worse in the feature space than that in the input space in some cases and demonstrate that the proposed kernel optimization algorithm can enlarge class separability. The second experiment is carried out on MSTAR SAR images using KOPCA compared with conventional KPCA to extract features and use nearest neighbor (NN) classifier to implement pattern classification. Simultaneously, sparse representation-based classifier (SRC) is applied to verify its superiority and effectiveness to deal with pattern classification compared with other classifiers. In order to verify the sparsity via BPDN, we randomly choose a test sample and show its representation coefficients on the training set.


### 5.1. Kernel Optimization on Synthetic Gaussian Distributed Dataset

Before concentrating on optimizing the kernel in the empirical feature space, we use two simple datasets called Gaussian distribution data generated by computer to get intuition about the embedding of data in the feature space into the empirical feature space. More information about data embedding can be found in [20]. Figure 1(a) shows a 2-class 2-dim dataset containing 400 samples, whose coordinates are uncorrelated. Each class contains 200 samples and both are Gaussian distributions with parameters: μx=-2,  μy=0,  σx=2,  σy=1 and μx=2,  μy=0,  σx=1,  σy=2, respectively. Seeing this figure, there is some overlap between the two classes. Figure 1(b) shows the projection of the data into the empirical feature space onto the first two significant dimensions corresponding to the first two largest eigenvalues of K, when the polynomial kernel function k0(x,y)=(x,y)d with d=3 is used. Figure 1(c) shows the corresponding projection when the Gaussian kernel function k0(x,y)=exp(-(1/σ)∥x-y∥2) with σ=1.0×105 is employed. Both the two basic kernels are mentioned in formula (1). It is seen from Figures 1(b) and 1(c) that the class separability is worse in the feature space than that in the input space when adopting both the polynomial kernel and Gaussian kernel. Therefore, it is important to conduct kernel optimization. We will carry out an experiment later to demonstrate that when applying the kernel optimization algorithm in Section 2.3,  the measure for class separability is surely enlarged.2-Dim dataset and its projections in the feature space onto the first two significant dimensions. (a) Two classes of data samples with two Gaussian distributions. (b) 2-Dim projection in the feature space for polynomial kernel withd=3. (c) 2-Dim projection in the empirical feature space for Gaussian kernel with σ=1.0×105.
(a)
(b)
(c)In this experiment, we set parameterγ of the function k1(·) in formula (2) as γ=1e6 for the given polynomial kernel k0(x,y)=(x,y)3 and the given Gaussian kernel k0(x,y)=exp(-1.0×10-5∥x-y∥2). One-third of the synthetic data are randomly chosen to form the “empirical core” set {ai}. The initial learning rate η0 and total iteration number Q are set 0.1 and 200, respectively, in both the polynomial kernel and Gaussian kernel. Figures 2(a) and 2(b) show the projection of the data into empirical feature space onto the first two significant dimensions corresponding to the first two largest eigenvalues of K, when the polynomial kernel and Gaussian kernel are used as mentioned above. It is seen from Figure 2 that the proposed kernel optimization algorithm substantially improves the class separability of the data in the empirical feature space and, hence, in the feature space.Improvement of class separability via kernel optimization algorithm. (a) 2-Dim projection in the empirical feature space for polynomial basic kerneld=3. (b) 2-Dim projection in the empirical feature space for Gaussian basic kernel with σ=1.0×105.
(a)
(b)


### 5.2. KOPCA Criterion on MSTAR SAR Dataset

This experiment is conducted on MSTAR SAR image provided by Defense Advanced Research Project Agency and Air Force Research Laboratory (DARPA/AFRL). The data is the MSTAR public release subset in order to initiate Moving and Stationary Target Acquisition and Recognition project which has provided a unique opportunity to promote and assess progress in SAR ATR algorithm development.Since the characteristic in SAR image changes greatly with different aspect angles, a great many of images within one target-class were collected, where the poses lie between 0 and 360 degree.The vehicle in MSTAR SAR Dataset contains BMP2 (sn-c21, sn-9563, sn-9566) tracked Armored Personnel Carrier, BTR70 (sn-c71) wheeled Armored Personnel Carrier, and T72 (sn-132, sn-812, sn-s7) Main Battle Tank. Different serial numbers in one-target class mean that vehicles are variant with small differences in configuration, articulation under extended operating condition (EOC) [21]. Therefore, scattering centers of SAR images change so intensively that recognition ability decreases greatly, and in this sense, recognizing variants in SAR images is difficult.In this experiment, we select images of BMP2sn-c21, BTR70sn-c71 and T72sn-132 in 17 depression angle as the training samples (numbers of each class are 233, 233, 233). The testing samples are selected as BMP2 sn-9563, BMP2 sn-9566, and T72 sn-812, T72sn-s7 in 15 depression angle (numbers of each class are 195, 196, 195, 191). The testing targets have small configuration differences to the training targets. There is a need to explanation; in this paper, KOPCA extracts features of all MSTAR images with different aspect angles directly and the process does not need to form different aspect windows and before recognition, images are chipped into48*48 pixels.We set parameterγ of the function k1(·) in formula (2) as γ=1e6. The kernel functions are chosen as the polynomial kernel k0(x,y)=(x,y)d where d is from 1 to 10, and the Gaussian kernel k0(x,y)=exp(-∥x-y∥2/σ) where σ is from 1e1 to 1e10. One-third of the training data are chosen to form the “empirical core” set {ai}. The initial learning rate η0 and total iteration number Q are set 0.1 and 200, respectively, in both the polynomial kernel and Gaussian kernel. Moreover, the feature dimension and empirical feature dimension are set 100 in both KPCA and KOPCA criterion. In order to reflect the performance of optimizing kernel in real-world application, the simplest nearest neighbor (NN) classifier is selected.Suppose the distance between two samplesxi and xj is defined by d(xi,xj)=∥xi-xj∥1, where ∥·∥1 denotes l1-norm.Then, if a test samplex satisfies d(x,xj)=minid(x,xi), and xi belongs to class k, then x belongs to class k.Tables1 and 2 show the recognition rates of KPCA and KOPCA with polynomial kernel and Gaussian kernel using the nearest neighbor (NN) classifier, respectively. From them, we can see that using the proposed data-dependent kernel optimization algorithm with KPCA criterion, recognition rate can be increased 10%~15% in both polynomial kernel and Gaussian kernel compared with conventional KPCA in the whole process. The class separability in the empirical feature space is improved, and thus, recognition rate is improved.Table 1
Recognition rates of KPCA and KOPCA with polynomial kernel using NN classifier.
Polynomial kernel (d)
1
2
3
4
5
6
7
8
9
10
KPCA: NN
67.56
68.00
67.11
66.67
66.22
65.78
65.33
65.11
64.44
64.44
KOPCA: NN
77.78
77.56
77.56
77.11
77.11
76.67
76.00
75.56
75.33
74.67Table 2
Recognition rates of KPCA and KOPCA with Gaussian kernel using NN classifier.
Gaussian kernel (σ)
1e1
1e2
1e3
1e4
1e5
1e6
1e7
1e8
1e9
1e10
KPCA: NN
62.00
62.00
62.00
66.11
68.00
67.11
62.00
61.33
34.22
31.11
KOPCA: NN
75.11
75.33
75.33
77.56
80.00
77.78
76.67
75.56
45.33
44.89Now, we will conduct another experiment to discuss sparse representation-based classifier (SRC). In the first part, we validate its effectiveness to deal with pattern classification task after extracting features via KOPCA (KOPCA: SRC) when compared with other classifiers, such asK-nearest neighbor (KNN) classifier, support vector classifier (SVC), and linear regression classifier (LRC) [22]. In the second part, in order to verify the sparsity of sparse representation-based classifier (SRC) via BPDN, we randomly choose a testing sample and show its representation coefficients on the training set.Tables3 and 4, respectively, show the recognition rates of KOPCA with KNN, SVC, LRC, and SRC classifiers corresponding to polynomial kernel and Gaussian kernel.Table 3
Recognition rates of KOPCA with polynomial kernel using different classifier.
Polynomial kernel (d)
1
2
3
4
5
6
7
8
9
10
KOPCA: KNN
85.11
85.33
87.78
83.56
83.33
84.22
82.89
80.89
82.00
81.33
KOPCA: SVC
74.00
91.33
88.44
88.44
88.00
86.22
86.00
85.56
83.33
82.67
KOPCA: LRC
88.67
92.44
93.78
94.22
94.44
93.56
93.56
92.89
92.22
91.56
KOPCA: SRC
98.44
98.44
98.22
98.22
98.00
97.56
98.22
98.00
97.56
97.78Table 4
Recognition rates of KOPCA with Gaussian kernel using different classifier.
Gaussian kernel (σ)
1e1
1e2
1e3
1e4
1e5
1e6
1e7
1e8
1e9
1e10
KOPCA: KNN
85.33
86.67
86.67
86.44
84.44
85.11
85.56
85.33
50.00
43.11
KOPCA: SVC
89.33
89.78
89.78
89.78
89.78
89.33
89.78
58.44
33.33
33.33
KOPCA: LRC
96.89
96.89
96.68
96.68
96.89
55.78
55.78
55.78
55.33
35.78
KOPCA: SRC
94.89
94.89
94.89
94.89
95.33
95.33
95.56
95.33
68.00
55.78From Table3, we see that sparse representation-based classifier (SRC) outperforms other classifiers no matter what the order of polynomial kernel is. In the whole experiment process, the recognition rate of KOPCA: SRC achieves higher than 95% while others are lower than 95%. Only KOPCA: LRC is close to KOPCA: SRC, the others are lower than 10%, even 20% compared with it. Meanwhile, notice that there exists an interesting phenomenon, that is, though the order of polynomial kernel varies from 1 to 10, variations of recognition rates of all the algorithms are less than 10%. However, it is inapplicable to Gaussian kernel. From Table 4, we learn that KOPCA: SRC has the superiority and effectiveness, that is, (1) when parameter σ of Gaussian kernel is between 1e1 and 1e5, recognition rate of KOPCA: SRC is slightly lower than KOPCA: LRC, the difference is no more than 2%, but it is better than KOPCA: KNN and KOPCA: SVM. (2) Though, KOPCA: LRC performs well, but it has limitations when σ is equal or greater than 1e6 since the recognition rate degrades quickly and significantly, while KOPCA: SRC remains stable and superior. (3) The performance of all these algorithms decreases rapidly when σ is greater than 1e8 while KOPCA: SRC can still hold about 70%, the others are equal or lower than 50%.The basis pursuit (RB) method is introduced to optimize l1-norm based minimization problem in our experiment. Here, we randomly choose a testing sample in the third class. Intuitively, most nonzero representation coefficients for the testing sample lie in the range from 301 to 450 (since each class has 150 training samples, so the index for the third class is from 301 to 450). Fortunately, our result demonstrates it. From Figure3, we see that the representation coefficients are sparse with respect to the basis, that is, the training set. Moreover, the nonzero coefficients are mostly located in the range from 301 to 450. As the end, we are to say that BPDN algorithm is fast enough to perform our SAR images’ recognition and classification. The BPDN software package that we use is from the “L1 Homotopy” homepage: http://users.ece.gatech.edu/~sasif/homotopy/. The running time is in second level, which is as the same level as LRC and SVC.Figure 3
Representation coefficients to a chosen testing sample in the third class.Through the complete discussion above, we can come to the conclusion that optimizing kernel PCA can indeed enhance the class separability in the empirical feature space compared to conventional KPCA and thus improve recognition rate. In the meantime, sparse representation-based classifier is robust and of high efficiency for classification compared to other nice classifiers.


## 5.1. Kernel Optimization on Synthetic Gaussian Distributed Dataset

Before concentrating on optimizing the kernel in the empirical feature space, we use two simple datasets called Gaussian distribution data generated by computer to get intuition about the embedding of data in the feature space into the empirical feature space. More information about data embedding can be found in [20]. Figure 1(a) shows a 2-class 2-dim dataset containing 400 samples, whose coordinates are uncorrelated. Each class contains 200 samples and both are Gaussian distributions with parameters: μx=-2,  μy=0,  σx=2,  σy=1 and μx=2,  μy=0,  σx=1,  σy=2, respectively. Seeing this figure, there is some overlap between the two classes. Figure 1(b) shows the projection of the data into the empirical feature space onto the first two significant dimensions corresponding to the first two largest eigenvalues of K, when the polynomial kernel function k0(x,y)=(x,y)d with d=3 is used. Figure 1(c) shows the corresponding projection when the Gaussian kernel function k0(x,y)=exp(-(1/σ)∥x-y∥2) with σ=1.0×105 is employed. Both the two basic kernels are mentioned in formula (1). It is seen from Figures 1(b) and 1(c) that the class separability is worse in the feature space than that in the input space when adopting both the polynomial kernel and Gaussian kernel. Therefore, it is important to conduct kernel optimization. We will carry out an experiment later to demonstrate that when applying the kernel optimization algorithm in Section 2.3,  the measure for class separability is surely enlarged.2-Dim dataset and its projections in the feature space onto the first two significant dimensions. (a) Two classes of data samples with two Gaussian distributions. (b) 2-Dim projection in the feature space for polynomial kernel withd=3. (c) 2-Dim projection in the empirical feature space for Gaussian kernel with σ=1.0×105.
(a)
(b)
(c)In this experiment, we set parameterγ of the function k1(·) in formula (2) as γ=1e6 for the given polynomial kernel k0(x,y)=(x,y)3 and the given Gaussian kernel k0(x,y)=exp(-1.0×10-5∥x-y∥2). One-third of the synthetic data are randomly chosen to form the “empirical core” set {ai}. The initial learning rate η0 and total iteration number Q are set 0.1 and 200, respectively, in both the polynomial kernel and Gaussian kernel. Figures 2(a) and 2(b) show the projection of the data into empirical feature space onto the first two significant dimensions corresponding to the first two largest eigenvalues of K, when the polynomial kernel and Gaussian kernel are used as mentioned above. It is seen from Figure 2 that the proposed kernel optimization algorithm substantially improves the class separability of the data in the empirical feature space and, hence, in the feature space.Improvement of class separability via kernel optimization algorithm. (a) 2-Dim projection in the empirical feature space for polynomial basic kerneld=3. (b) 2-Dim projection in the empirical feature space for Gaussian basic kernel with σ=1.0×105.
(a)
(b)


## 5.2. KOPCA Criterion on MSTAR SAR Dataset

This experiment is conducted on MSTAR SAR image provided by Defense Advanced Research Project Agency and Air Force Research Laboratory (DARPA/AFRL). The data is the MSTAR public release subset in order to initiate Moving and Stationary Target Acquisition and Recognition project which has provided a unique opportunity to promote and assess progress in SAR ATR algorithm development.Since the characteristic in SAR image changes greatly with different aspect angles, a great many of images within one target-class were collected, where the poses lie between 0 and 360 degree.The vehicle in MSTAR SAR Dataset contains BMP2 (sn-c21, sn-9563, sn-9566) tracked Armored Personnel Carrier, BTR70 (sn-c71) wheeled Armored Personnel Carrier, and T72 (sn-132, sn-812, sn-s7) Main Battle Tank. Different serial numbers in one-target class mean that vehicles are variant with small differences in configuration, articulation under extended operating condition (EOC) [21]. Therefore, scattering centers of SAR images change so intensively that recognition ability decreases greatly, and in this sense, recognizing variants in SAR images is difficult.In this experiment, we select images of BMP2sn-c21, BTR70sn-c71 and T72sn-132 in 17 depression angle as the training samples (numbers of each class are 233, 233, 233). The testing samples are selected as BMP2 sn-9563, BMP2 sn-9566, and T72 sn-812, T72sn-s7 in 15 depression angle (numbers of each class are 195, 196, 195, 191). The testing targets have small configuration differences to the training targets. There is a need to explanation; in this paper, KOPCA extracts features of all MSTAR images with different aspect angles directly and the process does not need to form different aspect windows and before recognition, images are chipped into48*48 pixels.We set parameterγ of the function k1(·) in formula (2) as γ=1e6. The kernel functions are chosen as the polynomial kernel k0(x,y)=(x,y)d where d is from 1 to 10, and the Gaussian kernel k0(x,y)=exp(-∥x-y∥2/σ) where σ is from 1e1 to 1e10. One-third of the training data are chosen to form the “empirical core” set {ai}. The initial learning rate η0 and total iteration number Q are set 0.1 and 200, respectively, in both the polynomial kernel and Gaussian kernel. Moreover, the feature dimension and empirical feature dimension are set 100 in both KPCA and KOPCA criterion. In order to reflect the performance of optimizing kernel in real-world application, the simplest nearest neighbor (NN) classifier is selected.Suppose the distance between two samplesxi and xj is defined by d(xi,xj)=∥xi-xj∥1, where ∥·∥1 denotes l1-norm.Then, if a test samplex satisfies d(x,xj)=minid(x,xi), and xi belongs to class k, then x belongs to class k.Tables1 and 2 show the recognition rates of KPCA and KOPCA with polynomial kernel and Gaussian kernel using the nearest neighbor (NN) classifier, respectively. From them, we can see that using the proposed data-dependent kernel optimization algorithm with KPCA criterion, recognition rate can be increased 10%~15% in both polynomial kernel and Gaussian kernel compared with conventional KPCA in the whole process. The class separability in the empirical feature space is improved, and thus, recognition rate is improved.Table 1
Recognition rates of KPCA and KOPCA with polynomial kernel using NN classifier.
Polynomial kernel (d)
1
2
3
4
5
6
7
8
9
10
KPCA: NN
67.56
68.00
67.11
66.67
66.22
65.78
65.33
65.11
64.44
64.44
KOPCA: NN
77.78
77.56
77.56
77.11
77.11
76.67
76.00
75.56
75.33
74.67Table 2
Recognition rates of KPCA and KOPCA with Gaussian kernel using NN classifier.
Gaussian kernel (σ)
1e1
1e2
1e3
1e4
1e5
1e6
1e7
1e8
1e9
1e10
KPCA: NN
62.00
62.00
62.00
66.11
68.00
67.11
62.00
61.33
34.22
31.11
KOPCA: NN
75.11
75.33
75.33
77.56
80.00
77.78
76.67
75.56
45.33
44.89Now, we will conduct another experiment to discuss sparse representation-based classifier (SRC). In the first part, we validate its effectiveness to deal with pattern classification task after extracting features via KOPCA (KOPCA: SRC) when compared with other classifiers, such asK-nearest neighbor (KNN) classifier, support vector classifier (SVC), and linear regression classifier (LRC) [22]. In the second part, in order to verify the sparsity of sparse representation-based classifier (SRC) via BPDN, we randomly choose a testing sample and show its representation coefficients on the training set.Tables3 and 4, respectively, show the recognition rates of KOPCA with KNN, SVC, LRC, and SRC classifiers corresponding to polynomial kernel and Gaussian kernel.Table 3
Recognition rates of KOPCA with polynomial kernel using different classifier.
Polynomial kernel (d)
1
2
3
4
5
6
7
8
9
10
KOPCA: KNN
85.11
85.33
87.78
83.56
83.33
84.22
82.89
80.89
82.00
81.33
KOPCA: SVC
74.00
91.33
88.44
88.44
88.00
86.22
86.00
85.56
83.33
82.67
KOPCA: LRC
88.67
92.44
93.78
94.22
94.44
93.56
93.56
92.89
92.22
91.56
KOPCA: SRC
98.44
98.44
98.22
98.22
98.00
97.56
98.22
98.00
97.56
97.78Table 4
Recognition rates of KOPCA with Gaussian kernel using different classifier.
Gaussian kernel (σ)
1e1
1e2
1e3
1e4
1e5
1e6
1e7
1e8
1e9
1e10
KOPCA: KNN
85.33
86.67
86.67
86.44
84.44
85.11
85.56
85.33
50.00
43.11
KOPCA: SVC
89.33
89.78
89.78
89.78
89.78
89.33
89.78
58.44
33.33
33.33
KOPCA: LRC
96.89
96.89
96.68
96.68
96.89
55.78
55.78
55.78
55.33
35.78
KOPCA: SRC
94.89
94.89
94.89
94.89
95.33
95.33
95.56
95.33
68.00
55.78From Table3, we see that sparse representation-based classifier (SRC) outperforms other classifiers no matter what the order of polynomial kernel is. In the whole experiment process, the recognition rate of KOPCA: SRC achieves higher than 95% while others are lower than 95%. Only KOPCA: LRC is close to KOPCA: SRC, the others are lower than 10%, even 20% compared with it. Meanwhile, notice that there exists an interesting phenomenon, that is, though the order of polynomial kernel varies from 1 to 10, variations of recognition rates of all the algorithms are less than 10%. However, it is inapplicable to Gaussian kernel. From Table 4, we learn that KOPCA: SRC has the superiority and effectiveness, that is, (1) when parameter σ of Gaussian kernel is between 1e1 and 1e5, recognition rate of KOPCA: SRC is slightly lower than KOPCA: LRC, the difference is no more than 2%, but it is better than KOPCA: KNN and KOPCA: SVM. (2) Though, KOPCA: LRC performs well, but it has limitations when σ is equal or greater than 1e6 since the recognition rate degrades quickly and significantly, while KOPCA: SRC remains stable and superior. (3) The performance of all these algorithms decreases rapidly when σ is greater than 1e8 while KOPCA: SRC can still hold about 70%, the others are equal or lower than 50%.The basis pursuit (RB) method is introduced to optimize l1-norm based minimization problem in our experiment. Here, we randomly choose a testing sample in the third class. Intuitively, most nonzero representation coefficients for the testing sample lie in the range from 301 to 450 (since each class has 150 training samples, so the index for the third class is from 301 to 450). Fortunately, our result demonstrates it. From Figure3, we see that the representation coefficients are sparse with respect to the basis, that is, the training set. Moreover, the nonzero coefficients are mostly located in the range from 301 to 450. As the end, we are to say that BPDN algorithm is fast enough to perform our SAR images’ recognition and classification. The BPDN software package that we use is from the “L1 Homotopy” homepage: http://users.ece.gatech.edu/~sasif/homotopy/. The running time is in second level, which is as the same level as LRC and SVC.Figure 3
Representation coefficients to a chosen testing sample in the third class.Through the complete discussion above, we can come to the conclusion that optimizing kernel PCA can indeed enhance the class separability in the empirical feature space compared to conventional KPCA and thus improve recognition rate. In the meantime, sparse representation-based classifier is robust and of high efficiency for classification compared to other nice classifiers.


## 6. Conclusion

In this paper, we proposed an efficient pattern classification method named kernel optimized PCA with sparse representation classifier (KOPCA: SRC). After conducting several experiments, we can come to the following conclusions with the experimental results.(1)
We have proposed a new space called the empirical feature space, in which the data is embedded in a way that the geometrical structure of the data in the feature space is preserved.(2)
We have presented a general form of data-dependent kernel and derived an effective algorithm for optimizing kernel by maximizing class separability of the dataset in the empirical feature space via Fisher criterion.(3)
We have for the first time applied sparse representation-based classifier for pattern classification on MSTAR SAR image and experiment results reveal that it is more effective and robust than existing classifiers.



---

*Source: 847062-2013-05-07.xml*