# A Jacobi-Davidson Method for Large Scale Canonical Correlation Analysis
## 3 The Main Algorithm
### Subspace Extraction
To see this, we notice that any \(\widetilde{U}_{j}\) and \(\widetilde{V}_{j}\) in (15) can be written as  
\[\widetilde{U}_{j}=U\widehat{U}_{j}\quad\text{and}\quad\widetilde{V}_{j}=V \widehat{V}_{j}\]  
for some \(\widehat{U}_{j}\in\mathbb{R}^{k\times j}\) and \(\widehat{V}_{j}\in\mathbb{R}^{k\times j}\) with \(\widehat{U}_{j}^{\text{T}}\widehat{U}_{j}=\widehat{V}_{j}^{\text{T}}\widehat{ V}_{j}=I_{j}\), and vice versa. Therefore the quantity in (15) is equal to  
\[\max_{\widehat{U}_{j}^{\text{T}}\widehat{U}_{j}=\widetilde{V}_{j}^{\text{T}} \widehat{V}_{j}=I_{j}}\;\sum_{i=1}^{j}\sigma_{i}(\widehat{U}^{\text{T}}U^{ \text{T}}CV\widehat{V}),\]  
which is \(\sum_{i=1}^{j}\theta_{i}\) by the proposition of the singular value decomposition of \(U^{\text{T}}CV\)[30]. The maximum is attended at \(\widehat{U}_{j}=[\hat{u}_{1},\hat{u}_{2},\ldots,\hat{u}_{i}]\) and \(\widehat{V}_{j}=[\hat{v}_{1},\hat{v}_{2},\ldots,\hat{v}_{j}]\). Therefore naturally, the best approximations to \((\lambda_{i},z_{i})\) (\(1\leq i\leq j\)) in the sense of (15) are given by \[(\theta_{i},z_{i}),\quad\text{where}\quad\bar{z}_{i}= \begin{bmatrix}\bar{x}_{i}\\ \bar{y}_{i}\end{bmatrix} ,\,\bar{x}_{i}=U\hat{u}_{i}\quad\text{and}\quad\bar{y}_ {i}=V\hat{v}_{i}. \tag{16}\]  
Define the residual  
\[r_{i}:=K\bar{z}_{i}-\theta_{i}M\bar{z}_{i}= \begin{bmatrix}0&C\\ C^{\text{T}}&0\end{bmatrix}\begin{bmatrix}\bar{x}_{i}\\ \bar{y}_{i}\end{bmatrix} -\theta_{i} \begin{bmatrix}A&0\\ 0&B\end{bmatrix}\begin{bmatrix}\bar{x}_{i}\\ \bar{y}_{i}\end{bmatrix} = \begin{bmatrix}r_{i}^{(0)}\\ r_{i}^{(0)}\end{bmatrix} , \tag{17}\]  
where \(K\) and \(M\) defined in (4), \(r_{s}^{(0)}=C\bar{y}_{i}-\theta_{i}A\bar{x}_{i}\) and \(r_{s}^{(0)}=C^{\text{T}}\bar{x}_{i}-\theta_{i}B\bar{y}_{i}\). It is noted that  
\[U^{\text{T}}r_{s}^{(0)}=U^{\text{T}}(C\bar{y}_{i}-\theta_{i}A\bar{x}_{i})=U^{ \text{T}}CV\hat{v}_{i}-\theta_{i}U^{\text{T}}AU\hat{u}_{i}=0\]  
and similarly \(V^{\text{T}}r_{s}^{(0)}\)=0. We summarize what we do in this subsection in the following theorem. **Theorem 2**. : _Suppose \(\{\mathcal{U},\mathcal{V}\}\) is a pair of approximate deflating subspaces with \(\dim(\mathcal{U})=\dim(\mathcal{V})=k\). Let \(U\in\mathbb{R}^{m\times k}\) and \(V\in\mathbb{R}^{n\times k}\) be the \(A\)- and \(B\)-orthonormal basis matrices of the subspaces \(\mathcal{U}\) and \(\mathcal{V}\), respectively. Denote \(\theta_{i}\), \(i=1,2,\ldots,k\) the singular values of \(U^{\text{T}}CV\) in descending order. Then, for any \(j\leq k\),_  
\[\sum_{i=1}^{j}\theta_{i}=\max_{ \begin{subarray}{c}\text{span}(\bar{y}_{i}) \subseteq I\text{span}(\bar{y}_{i})\subseteq V\\ \bar{U}_{j}^{\text{T}}AU\bar{y}_{j}^{\text{T}}\bar{y}_{j}\cap j-j\end{subarray}  }\,\,\sum_{i=1}^{j}\sigma_{i}(\bar{U}_{j}^{\text{T}}C\bar{V}_{j}),\]  
_the best approximations to the eigenpairs \((\lambda_{i},z_{i})\) (\(1\leq i\leq j\)) in the sense of (15) are \((\theta_{i},\bar{z}_{i})\) (\(1\leq i\leq j\)) given by (16), and the associated residuals defined in (17) admit \(r_{s}^{(0)}\perp\mathcal{U}\) and \(r_{s}^{(0)}\perp\mathcal{V}\)._