# Semi-Supervised Ridge Regression with Adaptive Graph-Based Label Propagation
## 3 The Proposed Method
### Convergence Analysis  
The convergence of the updating rules in Equations (24), (30) and (37) is analyzed in this section. Similar to [50], the definition of the auxiliary function is first given:  
**Definition 1**. : \(\theta(u,u)\) _is an auxiliary function for \(\phi(u)\) if conditions \(\theta(u,u)\geq\phi(u)\) and \(\theta(u,u)=\phi(u)\) are satisfied._  
The auxiliary function plays a very important role in the following lemma. **Lemma 1**. : _If \(\theta\) is an auxiliary function of \(\phi\), then it is non-increasing with the following updating formula._  
\[u^{t+1}=\underset{i}{\text{argmin}}\theta(u,u^{t+1}) \tag{40}\]  
**Proof. **  
\[\phi(u^{t+1})\leq\theta(u^{t+1},u^{t})\leq\theta(u^{t},u^{t})=\phi(u^{t}) \tag{41}\]Firstly, we present the updating rule for \(S\) in Equation (24) which is exactly the updating in Equation (40) with a proper auxiliary function. Considering any element \(S_{ij}\) in \(S\), \(\phi_{ij}(S_{ij})\) denotes the part of the objective function of SSRR-AGLP, which is only relevant to \(S_{ij}\), as follows:  
\[\phi_{ij}(S_{ij})=[-2S^{T}X^{T}X+S^{T}X^{T}XS+\alpha ES+\beta QS]_{ij} \tag{42}\]  
\[\phi^{\prime}_{ij}(S_{ij})=[-2X^{T}X+2X^{T}XS+\alpha E+\beta Q]_{ij} \tag{43}\]  
\[\phi^{\prime\prime}_{ij}(S_{ij})=[2X^{T}X]_{ii} \tag{44}\]  
where \(\phi^{\prime}_{ij}(S_{ij})\) and \(\phi^{\prime\prime}_{ij}(S_{ij})\) are the first-order and second-order derivatives of the objective function with respect to \(S_{ij}\). \(\square\)  
**Lemma 2**. : _The function \(\phi_{ij}(S_{ij},S^{t}_{ij})\) is an auxiliary function for \(\phi_{ij}(S_{ij})\), which is formulated as:_  
\[\phi_{ij}(S_{ij},S^{t}_{ij})=\phi_{ij}(S^{t}_{ij})+\phi^{\prime}_{ij}(S^{t}_{ ij})(S_{ij}-S^{t}_{ij})+\frac{[X^{T}XS+\frac{\alpha}{2}E+\frac{\beta}{2}Q]}{S^{t}_ {ij}}(S_{ij}-S^{t}_{ij})^{2} \tag{45}\]  
**Proof. ** We first generate the Taylor series expansion of \(\phi_{ij}(S_{ij})\)  
\[ \begin{array}{l}\phi_{ij}(S_{ij})=\phi_{ij}(S^{t}_{ij})+\phi^{\prime}_{ij}(S ^{t}_{ij})(S_{ij}-S^{t}_{ij})+\phi^{\prime\prime}_{ij}(S^{t}_{ij})(S_{ij}-S^{ t}_{ij})^{2}\\ =\phi_{ij}(S^{t}_{ij})+\phi^{\prime}_{ij}(S^{t}_{ij})(S_{ij}-S^{t}_{ij})+\phi^ {\prime\prime}_{ij}(S^{t}_{ij})(S_{ij}-S^{t}_{ij})^{2}\end{array}  \tag{46}\]  
According to Equation (45), \(\phi_{ij}(S_{ij},S^{t}_{ij})\geq\phi_{ij}(S_{ij})\) is equivalent to  
\[\frac{[X^{T}XS+\frac{\alpha}{2}E+\frac{\beta}{2}Q]_{ij}}{S^{t}_{ij}}\geq[X^{T }X]_{ii} \tag{47}\]  
Then, we obtain  
\[[X^{T}XS]_{ij}=\sum_{l=1}^{n}{(X^{T}X)_{il}S_{lj}}\geq(X^{T}X)_{ii}S_{ij} \tag{48}\]  
Thus, Equation (47) holds and \(\phi_{ij}(S_{ij},S^{t}_{ij})\geq\phi_{ij}(S_{ij})\). Furthermore, we can see that \(\phi_{ij}(S_{ij},S^{t}_{ij})=\phi_{ij}(S_{ij})\). Secondly, we indicate the updating rule for \(F\) in Equation (30) which is exactly updating in Equation (40) with a proper auxiliary function. Considering any element \(F_{ij}\) in \(F\), \(\phi_{ij}(F_{ij})\) is used to show the part of the objective function of SSRR-AGLP which is only relevant to \(F_{ij}\), as follows:  
\[\phi_{ij}(F_{ij})=[FF^{T}-2P^{T}XF^{T}+\beta F(D-R)F^{T}+FUF^{T}-2 YUF^{T}]_{ij} \tag{49}\]  
\[\phi^{\prime}_{ij}(F_{ij})=[2F-2P^{T}X+2\beta F(D-R)+2 FU-2 YU]_{ij} \tag{50}\]  
\[\phi^{\prime\prime}_{ij}(F_{ij})=[2I+2\beta(D-R)+2U]_{jj} \tag{51}\]  
where \(\phi^{\prime}_{ij}(F_{ij})\) and \(\phi^{\prime\prime}_{ij}(F_{ij})\) are the first-order and second-order derivatives of the objective function with respect to \(F_{ij}\). \(\square\)  
**Lemma 3**. : _The function \(\phi_{ij}(F_{ij},F^{t}_{ij})\) is an auxiliary function for \(\phi_{ij}(F_{ij})\), which is defined as:_  
\[\phi_{ij}(F_{ij},F^{t}_{ij})=\phi_{ij}(F^{t}_{ij})+\phi^{\prime}_{ij}(F^{t}_{ ij})(F_{ij}-F^{t}_{ij})+\frac{[F+\beta FD+FU]}{F^{t}_{ij}}(F_{ij}-F^{t}_{ij})^{2} \tag{52}\]  
**Proof. ** First, the Taylor series expansion of \(\phi_{ij}(F_{ij})\) is:  
\[