# A Jacobi-Davidson Method for Large Scale Canonical Correlation Analysis
## 3 The Main Algorithm
### Correction Equation
\begin{bmatrix}U^{\mathrm{T}}R_{ \mathrm{A}}^{\mathrm{T}}&0\\ 0&V^{\mathrm{T}}R_{\mathrm{B}}^{\mathrm{T}}\end{bmatrix}\begin{bmatrix}0& \widetilde{C}\\ \widetilde{C}^{\mathrm{T}}&0\end{bmatrix}\begin{bmatrix}R_{\mathrm{A}}U&0\\ 0&R_{\mathrm{B}}V\end{bmatrix} ,\]

where \(R_{\mathrm{A}}\) and \(R_{\mathrm{B}}\) are defined in (5), and \(R_{\mathrm{A}}U\) and \(R_{\mathrm{B}}V\) satisfy \((R_{\mathrm{A}}U)^{\mathrm{T}}R_{\mathrm{A}}U=U^{\mathrm{T}}AU=I_{k}\) and \((R_{\mathrm{B}}V)^{\mathrm{T}}R_{\mathrm{B}}V=V^{\mathrm{T}}BV=I_{\ell}\), respectively. Hence, apply [PERSON]'s interlacing inequalities [30] (Corollary 4.4) for the symmetric eigenvalue problem to the matrices \( \begin{bmatrix}0&\widetilde{C}\\ \widetilde{C}^{\mathrm{T}}&0\end{bmatrix} \) and \( \begin{bmatrix}0&U^{\mathrm{T}}CV\\ V^{\mathrm{T}}C^{\mathrm{T}}U&0\end{bmatrix} \), to get \(\lambda_{i}\geq\sigma_{i}(U^{\mathrm{T}}CV)\) for \(1\leq i\leq\min\{k,\ell\}\) and consequently

\[\sum_{i=1}^{\min\{k,\ell\}}\lambda_{i}\geq\max\sum_{i=1}^{\min\{k,\ell\}} \sigma_{i}(U^{\mathrm{T}}CV)\] (A1)

for any \(U\in\mathbb{R}^{m\times k}\) and \(V\in\mathbb{R}^{n\times\ell}\) such that \(U^{\mathrm{T}}AU=I_{k}\) and \(V^{\mathrm{T}}BV=I_{\ell}\). On the other hand, let \(U=[x_{1},x_{2},\dots,x_{k}]\) and \(V=[y_{1},y_{2},\dots,y_{\ell}]\) where \(x_{i}\) and \(y_{i}\) are defined in (10). Then, by (11), we have \(U^{\mathrm{T}}AU=I_{k}\) and \(V^{\mathrm{T}}BV=I_{\ell}\). Furthermore,

\[U^{\mathrm{T}}CV=[p_{1},p_{2},\dots,p_{k}]^{\mathrm{T}}\,\widetilde{C}\,[q_{1},q_{2},\dots,q_{\ell}]=\text{diag}(\lambda_{1},\dots,\lambda_{\min\{k,\ell\}} )\in\mathbb{R}^{k\times\ell}\]

which to give \(\sigma_{i}(U^{\mathrm{T}}CV)=\lambda_{i}\) for \(1\leq i\leq\min\{k,\ell\}\) and thus \[\sum_{i=1}^{\min\{k,\ell\}}\lambda_{i}\leq\max_{U^{\mathsf{T}}AU=I_{k},V^{\mathsf{T} }BV=I_{\ell}}\sum_{i=1}^{\min\{k,\ell\}}\sigma_{i}(U^{\mathsf{T}}CV). \tag{12}\]

Equation (12) is a consequence of (11) and (12). Proof of Lemma 1.: Let \([w_{1}^{\mathsf{T}},w_{2}^{\mathsf{T}}]^{\mathsf{T}}\in\operatorname{span}(x)^{ \perp_{a}}\times\operatorname{span}(y)^{\perp_{s}}\) and it satisfies \(G[w_{1}^{\mathsf{T}},w_{2}^{\mathsf{T}}]^{\mathsf{T}}=0\). We will prove \([w_{1}^{\mathsf{T}},w_{2}^{\mathsf{T}}]^{\mathsf{T}}=0\). Since

\[G \begin{bmatrix}w_{1}\\ w_{2}\end{bmatrix} = \begin{bmatrix}I_{m}-Axx^{\mathsf{T}}&0\\ 0&I_{n}-Byy^{\mathsf{T}}\end{bmatrix}\begin{bmatrix}-\lambda A&C\\ C^{\mathsf{T}}&-\lambda B\end{bmatrix}\begin{bmatrix}w_{1}\\ w_{2}\end{bmatrix} ,\]

then we have

\[ \begin{bmatrix}-\lambda A&C\\ C^{\mathsf{T}}&-\lambda B\end{bmatrix}\begin{bmatrix}w_{1}\\ w_{2}\end{bmatrix} = \begin{bmatrix}\gamma_{1}Ax\\ \gamma_{2}By\end{bmatrix} ,\]

where \(\gamma_{1}=x^{\mathsf{T}}(Cw_{2}-\lambda Aw_{1})\) and \(\gamma_{2}=y^{\mathsf{T}}(C^{\mathsf{T}}w_{1}-\lambda Bw_{2})\), which leads to

\[ \begin{cases}Cw_{2}&=\lambda Aw_{1}+\gamma_{1}Ax,\\ C^{\mathsf{T}}w_{1}&=\lambda Bw_{2}+\gamma_{2}By,\end{cases} \quad\Rightarrow \quad \begin{cases}Cw_{2}&=\lambda R_{s}^{\mathsf{T}}R_{s}w_{1}+\gamma_{1}R_{s }^{\mathsf{T}}R_{s}x,\\ C^{\mathsf{T}}w_{1}&=\lambda R_{s}^{\mathsf{T}}R_{s}w_{2}+\gamma_{2}R_{s}^{ \mathsf{T}}R_{s}y.\end{cases}  \tag{13}\]

Let \(\tilde{w}_{1}=R_{s}w_{1}\) and \(\tilde{w}_{2}=R_{s}w_{2}\). Then the equality (13) can be rewritten as

\[ \begin{cases}\widetilde{C}\tilde{w}_{2}&=\lambda\tilde{w}_{1}+\gamma_{1}p,\\ \widetilde{C}^{\mathsf{T}}\tilde{w}_{1}&=\lambda\tilde{w}_{2}+\gamma_{2}q, \end{cases}  \tag{14}\]

where \(\widetilde{C}\), \(p\) and \(q\) are defined in (7). Multiply the first and second equations of (14) by \(\widetilde{C}^{\mathsf{T}}\) and \(\widetilde{C}\) from left, respectively, to get

\[