# Sparse Representation-Based SAR Image Target Classification on the 10-Class MSTAR Data Set
## 2 Sparse Representation-Based Classification  
As described in the previous section, the training set has been given and the goal of the classification is to decide the class of the unknown samples correctly. Assume that there are \(K\)-class targets, and the \(i-\;th\) class has \(n_{i}\) samples. If every sample is represented in the form of a vector, the \(n_{i}\) samples can be concatenated into a matrix \(\phi_{i}\in R^{m\times n_{i}}\):  
\[\phi_{i}=\left[\phi_{i,1},\cdots,\phi_{i,n_{i}}\right] \tag{1}\]  
where m is the dimension of the vector, and \(\phi_{i,j}\;\;\;(j=1,\cdots,n_{i})\) stands for \(j-th\) sample in the class \(i\). When the number of samples in class is sufficient, the test sample \(y\) belonging to class \(i\) can be well approximated by the linear combination of these samples:  
\[y=c_{i,1}\phi_{i,1}+\cdots+c_{i,n_{i}}\phi_{i,n_{i}} \tag{2}\]where \(c_{i,j}\quad(j=1,\cdots,n_{i})\) is the contribution of the \(j-th\) sample to reconstructing sample \(y\). However, the class to which the test sample \(y\) belongs is unknown, in fact. All matrices \(\phi_{i}\quad(i=1,\cdots,K)\) need to be concatenated to a big matrix \(\phi=\left[\phi_{1},\cdots,\phi_{K}\right]\in R^{m\times N}\) named dictionary, where \(N\) represents the number of training samples. So, the unknown sample \(y\) can be represented by all training samples:  
\[y=\phi x \tag{3}\]  
where \(x=\left[c_{1,1},\cdots,c_{1,n_{1}},\cdots,c_{i,1},\cdots,c_{i,n_{1}},\cdots,c_ {K,1},\cdots,c_{K,n_{K}}\right]\) is the weight vector. Thanks to the sufficient samples in every class, the weight vector \(x\) is expected to be \(x~{}=~{}\left[0,\cdots,0,c_{i,1},\cdots,c_{i,n_{i}},0,\cdots,0\right]\). In other words, the test sample \(y\) can be well approximated by the samples, which belong to the same class as \(y\), and additionally, \(y\) has no relationship with the other samples, ideally. Considering the formulation in Equation, the test sample \(y\) and dictionary \(\phi\) are given, and the weight vector \(x\) is to be solved. Moreover, the solution \(x\) varies with the dictionary \(\phi\in R^{m\times~{}N}\). When \(m>N\), the equality is an overdetermined system, so the unique solution \(x\) can be obtained by solving the formulation. In most cases, however, the equality is an underdetermined system, _i.e._, \(m<N\), thus there are many solutions meeting the formulation. Therefore, a regularization constraint is needed to sift the optimal solution. Since a test sample \(y\) can be well represented by the training samples from the same class, the weight vector \(x\) is expected to have a lot of zero entries, _i.e._, \(x\) is sparse. So, the regularization constraint can be defined as \(l_{0}-norm\) minimization, that is:  
\[\min_{x}\left|\right|x\left|\right|_{0}\qquad\text{s.t.}\quad y=\phi x \tag{4}\]  
where \(\left|\right|x\left|\right|_{0}\) counts the number of non-zero entries in vector \(x\) Given that the test sample \(y\) is represented approximately by the training samples, the equality constraint in Equation (4) allows a small error. So the expression in Equation (4) can be rewritten as:  
\[\min_{x}\left|\right|x\left|\right|_{0}\qquad\text{s.t.}\quad\left|\right|y- \phi x\left|\right|\right|_{2}\leq\epsilon \tag{5}\]  
where \(\epsilon\) is the allowed error, which is a small positive integer. Solving the \(l_{0}-norm\) minimization in Equations(4) or Equation (5), however, is a NP-hard problem, which can be solved by OMP [11], and only an approximate solution will be acquired. Fortunately, it has been proved that if \(x\) is sparse enough, the optimization problem can relaxed to \(l_{0}-norm\) minimization:  
\[\min_{x}\left|\right|x\left|\right|_{1}\qquad\text{s.t.}\quad y=\phi x \tag{6}\] \[\min_{x}\left|\right|x\left|\right|_{1}\qquad\text{s.t.}\quad \left|\right|y-\phi x\left|\right|_{2}\leq\epsilon\]  
In this article, the second formulation in Equation (6) is taken into consideration, and the method to solve the minimization adopted here is second-order cone programs (SOCP) [13].