# Semi-Supervised Ridge Regression with Adaptive Graph-Based Label Propagation
## 3 The Proposed Method
### Objective Function of SSRR-AGLP
Subsequently, let \(F=[f_{1},f_{2},...,f_{n}]\in R^{c\times n}\) denote the prediction label matrix, where \(f_{i}\in R^{c\times 1}\) is the column vector that denotes the probability of the sample \(x_{i}\) belonging to each class. For example, the largest value of \(f_{ij}\) means the highest probability of the sample \(x_{i}\) belonging to \(j\)-th class. In terms of the LP theory [37; 38], the nearby or similar samples and the samples from the same global cluster should share similar labels. Therefore, the objective function of LP is defined as follows:  
\[\underset{F}{\text{min}}\ \varphi(F)=\sum_{i=1}^{n}\sum_{j=1}^{n}||f_{i}-f_{j}||_{ 2}^{2}R_{ij} \tag{13}\]  
where \(R=(S+S^{T})/2\) denotes the weight matrix. Moreover, in order to make the predicted labels and true labels of labeled samples be close as possible, we introduce the penalty constrain term as:  
\[\underset{F}{\text{min}}\ \vartheta(F)=\sum_{i=1}^{n}||f_{i}-y_{i}||_{2}^{2}u_{ii} \tag{14}\]where \(U\) is a selection diagonal matrix and element \(u_{ij}\) is defined as follows:  
\[u_{ii}=\left\{ \begin{array}{l}+\infty,\text{ if }x_{i}\text{ is a labeled sample}\\ 0,\text{ otherwise}\end{array} \right. \tag{15}\]  
Combining Equations (12)-(14), the adaptive graph label propagation model is defined as follows:  
\[ \begin{split}&\min_{F,S}\varphi(F,S)=||X-XS||_{2}^{2}+\alpha||E \odot S||_{1}+\beta\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}||f_{i}-f_{j}||_{ 2}^{2}R_{ij}+\sum\limits_{i=1}^{n}||f_{i}-y_{i}||_{2}^{2}u_{ii}\\ & s.t.F\geq 0,S\geq 0\end{split}  \tag{16}\]  
where \(\beta>0\) is a balance parameter which controls the importance of the label propagation term. The second aim of our proposed  
Through a series of algebraic formulations, Equation (19) is simplified to  
\[ \begin{array}{l}\min_{S}\varepsilon(S)=tr(X^{T}X-2S^{T}X^{T}X+S^{T}X^{T}XS)+ \alpha tr(ES)+\beta tr(QS)\\ \text{s.t.}\ S>0\end{array}  \tag{20}\]  
where \(Q=\left[q_{ij}\right]_{n\times n}\in R^{n\times n}\) and the element \(q_{ij}\) is defined as \(q_{ij}=||f_{i}-f_{j}||_{2}^{2}\). To solve the above problem, we need to introduce the Lagrange multiplier matrix \(\psi\). The Lagrange function of Equation (20) is:  
\[\eta(S,\psi)=tr(X^{T}X-2S^{T}X^{T}X+S^{T}X^{T}XS)+\alpha tr(ES)+\beta tr(QS)+ tr(\psi S) \tag{21}\]  
Setting the derivative with respect to \(S\) to zero, we obtain  
\[\frac{\partial\eta(S,\psi)}{\partial S}=-2X^{T}X+2X^{T}XS+\alpha E+\beta Q+\psi=0 \tag{22}\]  
According to the KKT condition \(\psi_{ij}S_{ij}=0\)[51], we obtain  
\[(-2X^{T}X+2X^{T}XS+\alpha E+\beta Q)_{ij}S_{ij}=0 \tag{23}\]  
According to Equation (23), the updating rule of \(S\) is  
\[S_{ij}=:S_{ij}\frac{\left[X^{T}X\right]_{ij}}{\left[X^{T}XS+\frac{\alpha}{2}E+ \frac{\beta}{2}Q\right]_{ij}} \tag{24}\]  
3.2.2 Fix Weight Matrix \(S\) and Transformation Matrix \(W\) to Solve Prediction Label Matrix \(F\)  
Removing the items that are not related to the matrix \(F\) in Equation (18), the optimization problem of the variable \(F\) can be obtained as follows:  
\[ \begin{array}{l}\min_{F}\varepsilon(F)=||F-W^{T}X||_{2}^{2}+\beta\sum\limits _{i=1}^{n}\sum\limits_{j=1}^{n}||f_{i}-f_{j}||_{2}^{2}R_{ij}+\sum\limits_{i=1}^ {n}||f_{i}-y_{i}||_{2}^{2}u_{ii}\\ \text{s.t.}\ F>0\end{array}  \tag{25}\]  
Through a series of algebra formulations, the Equation (25) is simplified to  
\[ \begin{array}{l}\min_{F}\varepsilon(F)=tr(FF^{T}-2P^{T}XF^{T}+P^{T}XX^{T}P)+ \beta tr(F(D-R)F^{T})+tr((F-Y)U(F-Y)^{T})\\ \text{s.t.}\ F>0\end{array}  \tag{26}\]  
where \(D\) is a diagonal matrix with its entries being \(D_{ii}=\sum_{j}^{n}R_{ij}\). To solve the problem of Equation (26), we also need to introduce the Lagrange multiplier matrix \(\Lambda\). The Lagrange function of Equation (26) is:  
\[ \begin{array}{l}\eta(F,\Lambda)\\ \eta(F,\Lambda)\\ \end{array}