## 2 Methodology
### Semi-Supervised Classification Based on Low Rank Representation  
Suppose there are \(N=l+u\) samples \(\mathbf{X}=[\mathbf{x}_{1};\mathbf{x}_{2};\dots;\mathbf{x}_{l};\mathbf{x}_{l+ 1};\dots;\mathbf{x}_{N}]\in R^{D\times N}\), where the first \(l\) samples are labeled and the left \(u\) samples are unlabeled. \(\mathbf{y}=[y_{1},y_{2},\dots,y_{N}]^{\mathrm{T}}\) is the label vector of labeled samples and \(y_{i}\) is the label of sample \(\mathbf{x}_{i}\). To perform multi-class classification, we extend the label vector \(\mathbf{y}\in\mathbb{R}^{N}\) into a label matrix \(\mathbf{Y}\in\mathbb{R}^{N\times C}\) as:  
\[\mathbf{Y}_{ic}= \begin{cases}1,&if\ y_{i}=c\\ 0,&otherwise\end{cases}  \tag{5}\]  
For unlabeled sample \(\mathbf{x}_{j}\), its corresponding label vector \(\mathbf{Y}_{j}\) is a zero vector. The general form of a linear classifier can be defined as:  
\[f(\mathbf{x})=\mathbf{W}^{T}\mathbf{x}+\mathbf{b} \tag{6}\]  
where \(\mathbf{W}\in R^{D\times C}\) is the predictive matrix, \(\mathbf{b}\in\mathbb{R}^{C}\) is the label bias, \(f(\mathbf{x})\in\mathbb{R}^{C}\) is the predicted likelihood vector for \(\mathbf{x}\) with respect to \(C\) different labels. Here, we consider a graph-regularized semi-supervised linear classifier as follows:  
\[J(\mathbf{W},\mathbf{b})=\arg\min_{\mathbf{W},\mathbf{b}}\frac{1}{l}\sum_{i=1 }^{l}\Psi(\mathbf{x_{i}},\mathbf{Y_{i}},f)+\frac{\alpha}{N^{2}}\|f\|_{I}^{2}+ \frac{\beta}{D^{2}}\|f\|_{H}^{2} \tag{7}\]  
where the first term is the empirical loss on labeled samples, the second term is to take advantage of the global structure of samples, the last term controls the complexity of \(f(\mathbf{x})\) and to avoid over-fitting. The first term is defined as follows:  
\[\sum_{i=1}^{l}\Psi(\mathbf{x_{i}},\mathbf{Y_{i}},f)=\sum_{i=1}^{l}\|\mathbf{ W}^{T}\mathbf{x_{i}}+\mathbf{b}-\mathbf{Y_{i}}\|^{2}=tr((\mathbf{W}^{T} \mathbf{X}+\mathbf{b}\mathbf{1}^{T}-\mathbf{Y}^{T})\mathbf{H}(\mathbf{W}^{T} \mathbf{X}+\mathbf{b}\mathbf{1}^{T}-\mathbf{Y}^{T})^{T}) \tag{8}\]  
where tr() is the matrix trace operator, \(\mathbf{H}\) is an \(N\times N\) diagonal matrix with \(\mathbf{H}_{ii}=1\) if \(\mathbf{x}_{i}\) is labeled, \(\mathbf{H}_{ii}\)=0 otherwise. \(\mathbf{1}\) is an \(N\)-dimensional vector with all elements are set to \(1\). The second term of Equation (7) can be computed as:  
\[\|f\|_{I}^{2} =\frac{1}{2}\sum_{i,j=1}^{N}\|f(\mathbf{x}_{i})-f(\mathbf{x}_{j} )\|^{2}\mathbf{S}_{ij}=\frac{1}{2}\sum_{i,j=1}^{N}\|\mathbf{W}^{T}\mathbf{x}_{ i}-\mathbf{W}^{T}\mathbf{x}_{j}\|^{2}\mathbf{S}_{ij} \tag{9}\] \[=tr(\mathbf{W}^{T}\sum_{i=1}^{N}(\mathbf{x_{i}}\mathbf{S}_{ii} \mathbf{x}_{i}^{T})\mathbf{W}-\mathbf{W}^{T}\sum_{i,j=1}^{N}(\mathbf{x_{i}} \mathbf{S}_{ij}\mathbf{x}_{j}^{T})\mathbf{W})\] \[=tr(\mathbf{W}^{T}(\mathbf{D}-\mathbf{S})\mathbf{X}^{T}\mathbf{W})\] \[=tr(\mathbf{W}^{T}\mathbf{X}\mathbf{L}\mathbf{X}^{T}\mathbf{W})\]  
where \(\mathbf{S}_{ij}\) is the weight of edge between \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\), \(\mathbf{S}=(\mathbf{Z}+\mathbf{Z}^{T})/2\) and \(\mathbf{Z}\) is the low rank representation coefficient matrix obtained from Equation (4). \(\mathbf{D}\) is a diagonal matrix with \(\mathbf{D}_{ii}=\sum\limits_{j=1}^{N}\mathbf{S}_{ij}\), \(\mathbf{L}=\mathbf{D}-\mathbf{S}\) is the graph Laplacian matrix [23].