# Relational Fisher Analysis: Dimensionality Reduction in Relational Data with Global Convergence +
## 3 Methodology
### Optimization of RFA  
We reformulate Problem (3) as  
\[\mathcal{L}=\min_{\mathbf{W}}\frac{\text{tr}(\mathbf{W}^{T}\mathbf{S}_{I} \mathbf{W})}{\text{tr}(\mathbf{W}^{T}\mathbf{S}_{P}\mathbf{W})}+\lambda\text {tr}(\mathbf{W}^{T}\mathbf{S}_{R}\mathbf{W}), \tag{4}\]  
where \(\mathbf{S}_{I}=\mathbf{X}\mathbf{L}_{I}\mathbf{X}^{T}\), \(\mathbf{S}_{P}=\mathbf{X}\mathbf{L}_{P}\mathbf{X}^{T}\) and \(\mathbf{S}_{R}=\mathbf{X}\mathbf{RX}^{T}\). As \(\mathbf{R}\) is psd, \(\mathbf{S}_{R}\) is as well. We suppose \(\mathbf{S}_{R}=\mathbf{U}\mathbf{A}\mathbf{U}^{T}\). We have  
\[\mathcal{L}=\min_{\mathbf{W}}\frac{\text{tr}(\mathbf{V}^{T}\mathbf{S}_{I} \mathbf{V})}{\text{tr}(\mathbf{V}^{T}\mathbf{S}_{P}\mathbf{V})}+\lambda\text{ tr}(\mathbf{V}^{T}\mathbf{V}), \tag{5}\]  
where \(\mathbf{W}=\mathbf{U}\mathbf{A}^{-1/2}\mathbf{V}\), \(\widetilde{\mathbf{S}}_{I}=\mathbf{\Lambda}^{-1/2}\mathbf{U}^{T}\mathbf{S}_{I} \mathbf{U}\mathbf{\Lambda}^{-1/2}\) and \(\widetilde{\mathbf{S}}_{P}=\mathbf{\Lambda}^{-1/2}\mathbf{U}^{T}\mathbf{S}_{ P}\mathbf{U}\mathbf{\Lambda}^{-1/2}\). Furthermore,  
\[\frac{\partial\mathcal{L}}{\partial\mathbf{V}}=\frac{2\text{tr}(\mathbf{V}^{T} \widetilde{\mathbf{S}}_{P}\mathbf{V})\widetilde{\mathbf{S}}_{I}\mathbf{V}-2 \text{tr}(\mathbf{V}^{T}\widetilde{\mathbf{S}}_{I}\mathbf{V})\widetilde{ \mathbf{S}}_{P}\mathbf{V}}{\text{tr}(\mathbf{V}^{T}\widetilde{\mathbf{S}}_{P} \mathbf{V})^{2}}+2\lambda\mathbf{V}. \tag{6}\]We let \(\frac{\partial\mathcal{L}}{\partial\widetilde{\mathbf{V}}}=\mathbf{0}\). We have  
\[\frac{\mathrm{tr}(\mathbf{V}^{T}\widetilde{\mathbf{S}}_{p}\mathbf{V}) \widetilde{\mathbf{S}}_{I}\mathbf{V}-\mathrm{tr}(\mathbf{V}^{T}\widetilde{ \mathbf{S}}_{I}\mathbf{V})\widetilde{\mathbf{S}}_{p}\mathbf{V}}{\mathrm{tr}( \mathbf{V}^{T}\widetilde{\mathbf{S}}_{p}\mathbf{V})^{2}}=-\lambda\mathbf{V}. \tag{7}\]  
Equation (7) can be rewritten as  
\[(\widetilde{\mathbf{S}}_{I}-\frac{\mathrm{tr}(\mathbf{V}^{T}\widetilde{ \mathbf{S}}_{I}\mathbf{V})}{\mathrm{tr}(\mathbf{V}^{T}\widetilde{\mathbf{S}}_{ p}\mathbf{V})}\widetilde{\mathbf{S}}_{p})\mathbf{V}=-\lambda\mathrm{tr}( \mathbf{V}^{T}\widetilde{\mathbf{S}}_{p}\mathbf{V})\mathbf{V}. \tag{8}\]  
We let \(\eta=\frac{\mathrm{tr}(\mathbf{V}^{T}\widetilde{\mathbf{S}}_{I}\mathbf{V})}{ \mathrm{tr}(\mathbf{V}^{T}\widetilde{\mathbf{S}}_{p}\mathbf{V})}\) and \(\widetilde{\lambda}=-\lambda\mathrm{tr}(\mathbf{V}^{T}\widetilde{\mathbf{S}}_ {p}\mathbf{V})\). We obtain  
\[(\widetilde{\mathbf{S}}_{I}-\eta\widetilde{\mathbf{S}}_{p})\mathbf{V}= \widetilde{\lambda}\mathbf{V}. \tag{9}\]  
It can be seen from Equation (9) that the columns of matrix \(\mathbf{V}\) are the eigenvectors of \(\widetilde{\mathbf{S}}_{I}-\eta\widetilde{\mathbf{S}}_{P}\), where \(\eta\) is a parameter related to \(\mathbf{V}\). Without loss of generality, we assume \(\mathbf{V}^{T}\mathbf{V}=\mathbf{I}_{d}\), where \(\mathbf{I}_{d}\) is an identity matrix. Hence, we have the following constrained trace ratio problem [33; 45]:  
\[\widetilde{\mathcal{L}}=\min_{\mathbf{V}^{T}\mathbf{V}=\mathbf{I}_{d}}\frac{ \mathrm{tr}(\mathbf{V}^{T}\widetilde{\mathbf{S}}_{I}\mathbf{V})}{\mathrm{tr}( \mathbf{V}^{T}\widetilde{\mathbf{S}}_{p}\mathbf{V})}. \tag{10}\]  
Problem (10) can be solved with the iterative method similar to that in [33; 45]. The specific steps are as follows:  
(1) **Removing the null space of \(\mathbf{S}_{t}=\widetilde{\mathbf{S}}_{I}+\widetilde{\mathbf{S}}_{p}\)[46]. ** We assume that \(\mathbf{S}_{t}=\widetilde{\mathbf{U}}\widetilde{\mathbf{A}}\widetilde{ \mathbf{U}}^{T}\), where \(\widetilde{\mathbf{A}}\) is a diagonal matrix and \(\widetilde{\mathbf{U}}\) contains the eigenvectors of \(\mathbf{S}_{t}\) corresponding to nonzero eigenvalues.