# A Jacobi-Davidson Method for Large Scale Canonical Correlation Analysis
## 3 The Main Algorithm
### Correction Equation  
In this subsection, we turn to construct a correction equation for a given eigenpair approximation. Suppose \((\theta,[\bar{x}^{\text{T}},\bar{y}^{\text{T}}]^{\text{T}})\) with \(\bar{x}^{\text{T}}A\bar{x}=\bar{y}^{\text{T}}B\bar{y}=1\) is an approximation of the eigenpair \((\lambda,[x^{\text{T}},y^{\text{T}}]^{\text{T}})\) of CCGEP (4), and \([r_{s}^{\text{T}},r_{s}^{\text{T}}]^{\text{T}}\) is the associated residual. We seek \(A\)- and \(B\)-orthogonal modifications of \(\bar{x}\) and \(\bar{y}\), respectively, such that  
\[ \begin{bmatrix}0&C\\ C^{\text{T}}&0\end{bmatrix}\begin{bmatrix}\bar{x}+s\\ \bar{y}+t\end{bmatrix} =\lambda \begin{bmatrix}A&0\\ 0&B\end{bmatrix}\begin{bmatrix}\bar{x}+s\\ \bar{y}+t\end{bmatrix} , \tag{18}\]  
where \(s\perp_{\alpha}\bar{x}\) and \(t\perp_{\alpha}\bar{y}\). Then, by (18), we have  
\[ \begin{bmatrix}-\lambda A&C\\ C^{\text{T}}&-\lambda B\end{bmatrix}\begin{bmatrix}s\\ t\end{bmatrix} =- \begin{bmatrix}r_{s}\\ r_{s}\end{bmatrix} +(\lambda-\theta) \begin{bmatrix}A&0\\ 0&B\end{bmatrix}\begin{bmatrix}\bar{x}\\ \bar{y}\end{bmatrix} . \tag{19}\]  
Notice that \(r_{s}\perp\bar{x}\) and \(r_{s}\perp\bar{y}\) by Theorem 2, which gives rise to  
\[ \begin{bmatrix}I_{m}-A\bar{x}\bar{x}^{\text{T}}&0\\ 0&I_{n}-B\bar{y}\bar{y}^{\text{T}}\end{bmatrix}\begin{bmatrix}r_{s}\\ r_{s}\end{bmatrix} = \begin{bmatrix}r_{s}\\ r_{s}\end{bmatrix} ,\quad \begin{bmatrix}I_{m}-A\bar{x}\bar{x}^{\text{T}}&0\\ 0&I_{n}-B\bar{y}\bar{y}^{\text{T}}\end{bmatrix}\begin{bmatrix}A\bar{x}\\ B\bar{y}\end{bmatrix} =0,\]  
and  
\[ \begin{bmatrix}I_{m}-A\bar{x}\bar{x}^{\text{T}}&0\\ 0&I_{n}-B\bar{y}\bar{y}^{\text{T}}\end{bmatrix}\begin{bmatrix}-\lambda A&C\\ C^{\text{T}}&-\lambda B\end{bmatrix}\begin{bmatrix}s\\ t\end{bmatrix} =- \begin{bmatrix}r_{s}\\ r_{s}\end{bmatrix} . \tag{20}\]  
Because \(s\perp_{\alpha}\bar{x}\) and \(t\perp_{\alpha}\bar{y}\), Equation (20) is rewritten as  
\[ \begin{bmatrix}I_{m}-A\bar{x}\bar{x}^{\text{T}}&0\\ 0&I_{n}-B\bar{y}\bar{y}^{\text{T}}\end{bmatrix}\begin{bmatrix}-\lambda A&C\\ C^{\text{T}}&-\lambda B\end{bmatrix}\begin{bmatrix}I_{m}-\bar{x}\bar{x}^{\text{T}}A&0\\ 0&I_{n}-\bar{y}\bar{y}^{\text{T}}B\end{bmatrix}\begin{bmatrix}s\\ t\end{bmatrix} =- \begin{bmatrix}r_{s}\\ r_{s}\end{bmatrix} . \tag{21}\]However, we do not know \(\lambda\) here. It is natural that we use \(\theta\) to replace \(\lambda\) in (21) to get the final correction equation, i.e., \[ \begin{bmatrix}I_{m}-A\tilde{x}\tilde{x}^{\mathrm{T}}&0\\ 0&I_{n}-B\tilde{y}\tilde{y}^{\mathrm{T}}\end{bmatrix}\begin{bmatrix}-\theta A& C\\ C^{\mathrm{T}}&-\theta B\end{bmatrix}\begin{bmatrix}I_{m}-\tilde{x}\tilde{x}^{ \mathrm{T}}A&0\\ 0&I_{n}-\tilde{y}\tilde{y}^{\mathrm{T}}B\end{bmatrix}\begin{bmatrix}s\\ t\end{bmatrix} =- \begin{bmatrix}r_{s}\\ r_{s}\end{bmatrix} .\] (22) We summarize what we have so far into Algorithm 1, and make a few comments on Algorithm 1. 1. At step 2, \(A\)- and \(B\)-orthogonality procedures are applied to make sure \(U^{\mathrm{T}}A\tilde{t}=0\) and \(V^{\mathrm{T}}Bs=0\). 2. At step 7, in most cases, the correct equation is not necessity to solve exactly. Some steps of iterative methods for symmetric linear systems, such as linear conjugate gradient method (CG) [34] or the minimum residual method (MINRES) [35], are sufficient. Usually, more steps in solving the correction equation lead to fewer outer iterations. This will be shown in numerical examples. 3. For the convergence test, we use the relative residual norms \[\eta(\theta_{i},\tilde{z}_{i}):=\frac{\|r_{s}^{0}\|_{1}+\|r_{s}^{0}\|_{1}}{(\|C \|_{1}+\theta_{i}\|A\|_{1})\|\tilde{x}_{i}\|_{1}+(\|C\|_{1}+\theta_{i}\|B\|_{ 1})\|\tilde{y}_{i}\|_{1}}\] (23) to determine if the approximate eigenparis \((\theta_{i},\tilde{z}_{i})\) has converged to a desired accuracy. In addition, in the practical implementation, once one or several of approximate eigenpairs converge to a preset accuracy, they should be deflated so that they will not be re-computed in the following iterations.