# Semi-Supervised Classification Based on Low Rank Representation
## 2 Methodology
### Low-Rank Representation for Graph Construction  
Let \(\mathbf{X}=[\mathbf{x}_{1};\mathbf{x}_{2};\mathbf{x}_{3};\dots;\mathbf{x}_{N}]\in \mathbb{R}^{D\times N}\) be a set of samples, each column \(\mathbf{x}_{i}\in\mathbb{R}^{D}\) represents a sample. Each sample can be viewed as a linear combination of bases from a dictionary \(\mathbf{A}=[\mathbf{a}_{1};\mathbf{a}_{2};\mathbf{a}_{3};\dots;\mathbf{a}_{N} ]\in\mathbb{R}^{D\times N}\). Similar to work in [13; 15], we set \(\mathbf{A}=\mathbf{X}\) in this paper. Low rank representation represents each sample by a linear combination of the bases in \(\mathbf{A}\) as follows:  
\[\mathbf{X}\mathbf{=}\mathbf{A}\mathbf{Z} \tag{1}\]  
where \(\mathbf{Z}=[\mathbf{z}_{1},\mathbf{z}_{2},\dots,\mathbf{z}_{N}]\in\mathbb{R}^ {N\times N}\) is the coefficient matrix of low-rank representation. Each element in \(\mathbf{z}_{i}\) can be viewed as the contribution to the reconstruction of \(\mathbf{x}_{i}\) with \(\mathbf{A}\) as the dictionary. \(\mathbf{A}\) is often over complete. Therefore, Equation (1) cannot be solved in finite steps. To overcome this problem, we enforce \(\mathbf{Z}\) to be low rank and solve the following optimization problem:  
\[\begin{cases}\underset{\mathbf{Z}}{\text{min}}\,rank(\mathbf{Z})\\ s.t.\,\mathbf{X}\mathbf{=}\mathbf{A}\mathbf{Z},\mathbf{Z}\geq 0\end{cases} \tag{2}\]  
Obviously, \(\mathbf{X}\) is reconstructed by the low rank constrained matrix \(\mathbf{Z}\) and the dictionary matrix \(\mathbf{A}\). Equation (2) is coined as low rank representation (LRR) [15]. \(\mathbf{Z}\geq 0\) is added since [PERSON] et al. In [18], it was observed that non-negative \(\mathbf{Z}\) often leads to improved performance for data representation and graph construction. However, Equation (2) is NP-hard. Fortunately, Equation (2) can be relaxed to the following problem:  
\[\begin{cases}\underset{\mathbf{Z}}{\text{min}}\,\|\mathbf{Z}\|_{*}\\ s.t.\mathbf{X}\mathbf{=}\mathbf{A}\mathbf{Z},\mathbf{Z}\geq 0\end{cases} \tag{3}\]  
where \(\|\mathbf{Z}\|_{*}\) is the nuclear norm of \(\mathbf{Z}\) and it is the sum of singular values of \(\mathbf{Z}\)[19]. Equation (3) can be solved by matrix completion methods [20]. Equation (3) can be further relaxed to take into account noisy features as follows:  
\[\begin{cases}\underset{\mathbf{Z}}{\text{min}}\,\|\mathbf{Z}\|_{*}+\lambda\| \mathbf{E}\|_{2,1}\\ s.t.\mathbf{X}\mathbf{=}\mathbf{A}\mathbf{Z}+\mathbf{E},\mathbf{Z}\geq 0\end{cases} \tag{4}\]  
where \(\|\mathbf{E}\|_{2,1}=\sum_{j=1}^{n}\sqrt{\sum_{i=1}^{m}(\mathbf{E}_{ij})^{2}}\) is called \(l_{2,1}\)-norm [21] and \(\lambda>0\) is used to balance the effect of noise. The \(l_{2,1}\)-norm encourages the columns of \(\mathbf{E}\) to be zero. To solve Equation (4), [PERSON] et al. [22] suggested a Linearized Alternating Direction Method with Adaptive Penalty(LADMAP) technique to iteratively optimize \(\mathbf{Z}\) and \(\mathbf{E}\) with each of them fixed as constant while optimizing the other. Next, each column of \(\mathbf{Z}^{*}\) is normalized via \(\mathbf{z}_{i}=\mathbf{z}_{i}/\|\mathbf{z}_{i}\|_{2}\), and then each negative entry of \(\mathbf{z}^{*}\) is set to zero. Low rank representation jointly finds the low-ranked coefficient matrix \(\mathbf{Z}\) for all samples in \(\mathbf{X}\). \(\mathbf{Z}\) can be used to define a low rank representation based undirected graph, whose weighted adjacent matrix is \(\mathbf{S}=(\mathbf{Z}+\mathbf{Z}^{T})/2\).