# One-Shot Distributed Generalized Eigenvalue Problem (DGEP): Concept, Algorithm and Experiments +
## 1 Introduction  
Nowadays, as the data dimension and quantity increases, distributed local servers are essential in storing large-scale data. The distributed framework enables many equivalent local servers to seek the solution to the same class of problems, where specific servers may provide insight for other servers. This process is usually achieved by iteratively exchanging information between local servers, namely, in multi-round communication, to partially improve the way they accomplish their tasks. As increasing scenarios, such as financial [1], medical [2], and biomedical [3] tasks, come into view, where they usually hold the sensitive and limited scale of datasets in a distributed manner, the distributed systems shall offer a relatively safe and efficient way to obtain a satisfying result. There have been many works on distributed systems in the past decades, especially in classification [4; 5] and regression [6; 7; 8; 9]. However, the discussion about distributed generalized eigenvalue problem (GEP) is rare. GEP is known as another important type of learning task that involves (generalized) eigenvalue decomposition (GED), including Singular Value Decomposition (SVD) [10], Principal Component Analysis (PCA) [11], Canonical Correlation Analysis (CCA) [12], etc. In optimization, such problems can be formulated in the following way:  
\[\max_{w\in\mathbb{R}^{d}}\quad w^{*}\,Aw\quad\text{s.t.}\,\,\,w^{*}\,Bw=1, \tag{1}\]  
where \(A\in\mathbb{R}^{d\times d}\) is a symmetric matrix, \(B\in\mathbb{R}^{d\times d}\) is a positive definite matrix, and \(w^{*}\) denotes the conjugate transpose matrix of \(w\). The optimization problem has an equivalent solution to \(\lambda_{max}(B^{-\frac{1}{2}}AB^{-\frac{1}{2}})\)[13], which pursues the maximum eigenvalue \(\lambda\) of the symmetric data covariance \(B^{-\frac{1}{2}}AB^{-\frac{1}{2}}\) with an invertible matrix \(B\). In short, (1) finds the generalizedeigenvector \(w\) corresponding to the largest eigenvalue of the data covariance. Then, we can build the relationship between GEP and GED. The Lagrangian for (1) is given by:  
\[L(w;\lambda)=w^{*}Aw-\lambda(w^{*}Bw-1),\]  
where \(\lambda\in\mathbf{R}\) is the Lagrange multiplier. By equating the derivation of Lagrangian to zero, we obtain the generalized eigenvalue decomposition as below:  
\[Aw=\lambda Bw, \tag{2}\]  
where \(w\in\mathbf{R}^{d}\) denotes the generalized eigenvector of GEP with respect to the generalized eigenvalue \(\lambda\). Since GEP plays a vital role in a large family of high-dimensional statistical models, distributed algorithms for GEP are desired. However, only some variant cases are discussed in the distributed manner. There are two common variants of GEP whose distributed algorithms are well studied. On the one hand, when the constraint of (1) is linear, distributed linearly constrained minimum variance (LCMV) is widely used in signal processing [14; 15] with the same objective function in beamforming. However, its algorithms cannot deal with quadratic constraints in GEP obviously. On the other hand, when \(B\) in (1) is an identity matrix, GEP turns to the ordinary eigenvalue problem (EP). Moreover, distributed algorithms for EP are numerous due to its good characteristics. Further in detail, when \(A\) is symmetric, it is PCA, and it is SVD otherwise. For one-shot communication with efficiency, distributed PCA algorithms are given in [16; 17; 18]. In addition, distributed SVD [19] conducts distributed averaging over measurement vectors in one-shot communication. For iterative communication, a distributed sparse PCA [20] is proposed based on the power method, which is numerically efficient for the large-scale data. In addition, distributed SVD methods in [21; 22] utilize the distributed power method in both the centralized and decentralized way. However, the distributed algorithms mentioned above cannot be used in distributed GEP because, in distributed systems, the sum of the local covariance matrices of GEP does not equal to the global centered covariance matrix while it equals in EP.