# One-Shot Distributed Generalized Eigenvalue Problem (DGEP): Concept, Algorithm and Experiments +
## 4 Distributed Canonical Correlation Analysis and Its Multiple Formulation  
In this section, we investigate distributed CCA, which is a special instance of distributed GEP. In the classical setting, the CCA finds the linear combinations of two sets of random variables with maximal correlation. Furthermore, multiple CCA [34] is the cornerstone of multi-view learning. However, if considering the original data from each view, Algorithm 1 encounters the theoretical barrier of convergence in solving the distributed CCA with the tool of the power method. So, we put forward a new algorithm based on Algorithm 1 when using the power method in this section. We first provide the mathematical formulation of CCA. Given \(d\) observations, denote \(X=(x_{1},\ldots,x_{d})\in\mathbf{R}^{n_{1}\times d}\), \(Y=(y_{1},\ldots,y_{d})\in\mathbf{R}^{n_{2}\times d}\). The covariances \(\Sigma_{XY}=\mathbf{E}(XY^{*})=XY^{*}\), \(\Sigma_{XX}=\mathbf{E}(XX^{*})=XX^{*}\) and \(\Sigma_{YY}=\mathbf{E}(YY^{*})=YY^{*}\). Without loss of generality, its multiple version is formulated as below:  
\[\max_{U,V} \mathrm{Trace}(U^{*}XY^{*}V)\] (7) s.t. \[U^{*}XX^{*}U=I_{k},\ U\in\mathbf{R}^{n_{1}\times k},\] \[V^{*}YY^{*}V=I_{k},\ V\in\mathbf{R}^{n_{2}\times k},\]  
where \(I_{k}\) stands for identity matrix, and its number of columns is \(k\), denoting the number of canonical components and normally \(k\leq min\{n_{1},n_{2}\}\). When \(k=1\), it degrades to the standard CCA. Recall from the formulation of CCA, we obtain:  
\[\max_{W\in\mathbf{R}^{d\times k}}\quad\mathrm{Trace}(W^{*}AW)\quad\text{s.t. }\ W^{*}BW=I_{k}, \tag{8}\]  
where \(A= \begin{pmatrix}0&XY^{*}\\ YX^{*}&0\end{pmatrix} \), \(B= \begin{pmatrix}XX^{*}&0\\ 0&YY^{*}\end{pmatrix} \), \(W= \begin{pmatrix}U&0\\ 0&V\end{pmatrix} \). This kind of self-adjoint structure keeps the symmetry of \(A\) and \(B\). However, according to Theorem 2 in [21], there must be an eigengap of \(M=B^{-\frac{1}{2}}AB^{-\frac{1}{2}}\in\mathbf{R}^{d\times d}\) when using the power method. Hence, using Algorithm 1 in distributed CCA may not only increase the approximation error during communication but also result in a convergence barrier for no eigengap. We will also illustrate this barrier in further numerical experiments. So, in this section, we reformulate CCA and put forward a one-shot distributed multiple CCA algorithm with the power method, which solves the inherent structure defect efficiently. The reformulated centered problem is shown as below:  
\[ \begin{split}\max_{W_{1},W_{2}}&\text{Trace}(W_{1}^{*} (XX^{*})^{-\frac{1}{2}*}XY^{*}(YY^{*})^{-\frac{1}{2}}W_{2})\\ \text{s.t.}& W_{1}^{*}W_{1}=I_{k},\quad W_{2}^{*}W_ {2}=I_{k},\end{split}  \tag{9}\]  
where \(X=[X_{1},X_{2},\dots,X_{N}]\) and \(Y=[Y_{1},Y_{2},\dots,Y_{N}]\) are concatenations of original data from \(N\) local servers. \(M_{0}=(XX^{*})^{-\frac{1}{2}*}XY^{*}(YY^{*})^{-\frac{1}{2}}\) is the asymmetric covariance of the centered problem. The distributed optimization problem is:  
\[ \begin{split}\max_{W_{1},W_{2}}&\text{Trace}\left( W_{1}^{*}\left(\sum_{i=1}^{N}M_{i}\right)W_{2}\right)\\ \text{s.t.}& W_{1}^{*}W_{1}=I_{k},\quad W_{2}^{*}W_ {2}=I_{k},\end{split}  \tag{10}\]  
where the covariance \(M_{i}=(X_{i}X_{i}^{*})^{-\frac{1}{2}*}X_{i}Y_{i}^{*}(Y_{i}Y_{i}^{*})^{-\frac{1 }{2}}\) for CCA is also asymmetric, and \(\hat{M}=\sum_{i=1}^{N}M_{i}\) is an approximation of \(M_{0}\) in the distributed setting. Then, we derive the one-shot distributed algorithm for multiple CCA in the following. Algorithm 3 shows the one-shot distributed multiple CCA algorithm which improves the performance by breaking the self-adjoint symmetric GEP structure. The power iterations in the central optimization are divided into two parts as computing the eigenspace of \(\hat{M}_{1}=\sum_{i=1}^{N}M_{i}M_{i}^{*}\) and \(\hat{M}_{2}=\sum_{i=1}^{N}M_{i}^{*}M_{i}\). The process can be viewed as seeking the left and right singular vector of the approximated covariance \(\hat{M}\) at the same time. QR factorization [30] is used to become the orthonormal approximated eigenspace.