# Semi-Supervised Ridge Regression with Adaptive Graph-Based Label Propagation
## 3 The Proposed Method
### Convergence Analysis
\begin{array}{l}\phi_{ij}(F_{ij})=\phi_{ij}(F_{ij}^{t})+\phi_{ij}^{\prime}(F_{ ij}^{t})(F_{ij}-F_{ij}^{t})+\phi_{ij}^{\prime\prime}(F_{ij}^{t})(F_{ij}-F_{ij}^{t})^{2} \\ =\phi_{ij}(F_{ij}^{t})+\phi_{ij}^{\prime}(F_{ij}^{t})(F_{ij}-F_{ij}^{t})+\phi_{ ij}^{\prime\prime}(F_{ij}^{t})(F_{ij}-F_{ij}^{t})^{2}\end{array}  \tag{53}\]  
According to Equation (52), \(\phi_{ij}(F_{ij},F_{ij}^{t})\geq\phi_{ij}(F_{ij})\) is equivalent to  
\[\frac{\left[F+\beta FD+FU\right]_{ij}}{F_{ij}^{t}}\geq\left[I+\beta(D-R)+U \right]_{ij} \tag{54}\]  
Then, we have  
\[\left[\beta FD\right]_{ij}=\beta\sum_{l=1}^{N}F_{il}^{t}D_{lj}\geq\beta F_{ij} ^{t}D_{jj}\geq\beta F_{ij}^{t}(D_{jj}-R_{jj}) \tag{55}\]  
\[\left[FU\right]_{ij}=\sum_{l=1}^{N}F_{il}^{t}U_{lj}\geq F_{ij}^{t}U_{lj} \tag{56}\]  
Thus, Equation (54) holds and \(\phi_{ij}(F_{ij},F_{ij}^{t})\geq\phi_{ij}(F_{ij})\). Furthermore, we can see that \(\phi_{ij}(F_{ij},F_{ij}^{t})=\phi_{ij}(F_{ij})\). Subsequently, we describe the updating rule for \(W\) in Equation (37), which is correctly updated in Equation (40) with a proper auxiliary function. For any element \(W_{ij}\) in \(W,\phi_{ij}(W_{ij})\) is adopted to represent the part of the objective function of SSRR-AGLP, which is only relevant to \(W_{ij}\). It is defined as:  
\[\phi_{ij}(W_{ij})=\left[-2W^{T}XF^{T}+W^{T}XX^{T}W+\gamma W^{T}W\right]_{ij} \tag{57}\]  
\[\phi_{ij}^{\prime}(W_{ij})=\left[-2 XF^{T}+2 XX^{T}W+2\gamma W\right]_{ij} \tag{58}\]  
\[\phi_{ij}^{\prime\prime}(W_{ij})=\left[2 XX^{T}+2\gamma I\right]_{jj} \tag{59}\]  
where \(\phi_{ij}^{\prime}(W_{ij})\) and \(\phi_{ij}^{\prime\prime}(W_{ij})\) are the first-order and second-order derivatives of the objective function with respect to \(W_{ij}\). \(\square\)  
**Lemma 4**. : _The function_  
\[\phi_{ij}(W_{ij},W_{ij}^{t})=\phi_{ij}(W_{ij}^{t})+\phi_{ij}^{\prime}(W_{ij}^ {t})(W_{ij}-W_{ij}^{t})+\frac{\left[XX^{T}W+\gamma W\right]}{W_{ij}^{t}}{\left( W_{ij}-W_{ij}^{t}\right)}^{2} \tag{60}\]  
_is an auxiliary function for \(\phi_{ij}(W_{ij})\)._  
**Proof. ** The Taylor series expansion of \(\phi_{ij}(W_{ij})\) is:  
\[ \begin{array}{l}\phi_{ij}(W_{ij})=\phi_{ij}(W_{ij}^{t})+\phi_{ij}^{\prime}(W _{ij}^{t})(W_{ij}-W_{ij}^{t})+\phi_{ij}^{\prime\prime}(W_{ij}^{t})(W_{ij}-W_{ ij}^{t})^{2}\\ =\phi_{ij}(W_{ij}^{t})+\phi_{ij}^{\prime}(W_{ij}^{t})(W_{ij}-W_{ij}^{t})+\phi_{ ij}^{\prime\prime}(W_{ij}^{t})(W_{ij}-W_{ij}^{t})^{2}\end{array}  \tag{61}\]  
From Equation (60), we can find that \(\phi_{ij}(W_{ij},W_{ij}^{t})\geq\phi_{ij}(W_{ij})\) is equivalent to  
\[\frac{\left[XX^{T}W+\gamma W\right]_{ij}}{W_{ij}^{t}}\geq\left[XX^{T}+\gamma I \right]_{ii} \tag{62}\]  
Then, we have  
\[\left[XX^{T}W\right]_{ij}=\sum_{l=1}^{d}\left(XX^{T}\right)_{il}^{t}W_{lj}\geq \left(XX^{T}\right)_{ii}^{t}W_{ij} \tag{63}\]Thus, Equation (62) holds and \(\vartheta_{ij}(W_{ij},W_{ij}^{t})\geq\phi_{ij}(W_{ij})\). Furthermore, we can see that \(\vartheta_{ij}(W_{ij},W_{ij}^{t})=\phi_{ij}(W_{ij})\). Finally, in order to demonstrate the convergence of the updating rules in Equations (24), (30) and (37), we give the following theorem about the three updating rules:  
**Theorem 1. **_For \(S\geq 0\), \(F\geq 0\) and \(W\geq 0\), the objective function in Equation (14) is non-increasing with the updating rules in Equations (24), (30) and (37)._  
**Proof of Theorem 1.