# One-Shot Distributed Generalized Eigenvalue Problem (DGEP): Concept, Algorithm and Experiments +
## 3 Approximation Error Analysis of Distributed GEP  
In this section, we analyze the approximation error of DGEP in Algorithm 1, which is defined as the distance \(\mathbf{D}\) between the centered ground truth \(W_{c}\) and the estimator \(\hat{W}\). Without loss of generality, the top \(k\) subspace distance, measured by the sine of the angle \(\theta_{k}\), is analyzed. Thus,  
\[\|\mathbf{D}_{k}(W_{c},\hat{W})\|=\sin(\theta_{k}(W_{c},\hat{W})),\]  
where \(W_{c},\hat{W}\in\mathcal{R}^{d\times k}\), norm \(\|\cdot\|\) denotes \(\ell_{2}\) norm as default, and \(\|\mathbf{D}_{k}(\cdot,\cdot)\|\) denotes the top \(k\) subspace distance. Our analysis is based on \(\sin\theta\) theorem in [33], which reveals how much the invariant subspace will be affected if the covariance matrix is slightly perturbed. We first define that the centered covariance before one-shot communication \(\Sigma_{1}=M_{0}\) and the approximation covariance in the center server \(\Sigma_{2}=\sum_{i=1}^{N}M_{i}\) are represented by the detailed data matrix multiplication of \(A_{i}\) and \(B_{i}\), respectively. The goal of Algorithm 1 is to learn a central orthonormal matrix \(\hat{W}\in\mathbf{R}^{d\times k}\) to estimate \(W_{c}\), which is the top \(k\) eigenspace of \(\Sigma_{1}\) and also the ground truth. Our main result is in the following. **Theorem 1**. : _Given matrices \(\Sigma_{1}\in\mathbf{R}^{d\times d}\) with eigenvalues \(\sigma_{1}\geq\cdots\geq\sigma_{d}\) and \(\Sigma_{2}\in\mathbf{R}^{d\times d}\) in the central server with eigenvalues \(\sigma_{1}\geq\cdots\geq\sigma_{d}\). For a given dimension \(k\), where \(k\leq d\), let \(W_{c}=(w_{1},\ldots,w_{k})\in\mathbf{R}^{d\times k}\) and \(\hat{W}=(\hat{w}_{1},\ldots,\hat{w}_{k})\in\mathbf{R}^{d\times k}\) have orthogonal columns satisfying \(\Sigma_{1}w_{j}=\sigma_{j}w_{j}\) and \(\Sigma_{2}\hat{w}_{j}=\sigma_{j}\hat{w}_{j}\) for \(j=1,\ldots,k\). Assume \(\Delta_{k}=inf\{\|\hat{\sigma}-\sigma|:\sigma\in[\sigma_{k},\sigma_{1}],\hat{ \sigma}\in[-\infty,\hat{\sigma}_{k+1}]\cup[\sigma_{0},\infty]\}\), where \(\hat{\sigma}_{0}=-\infty\) and \(\hat{\sigma}_{k+1}=\infty\) and \(\Delta_{k}>0\). The approximation error is upper-bounded by:_  
\[\left\|\mathbf{D}_{k}\left(W_{c},\hat{W}\right)\right\|\leq\frac{\max_{i}a_{ i}}{N^{3}\Delta_{k}\max_{j}b_{j}}+\frac{N}{\Delta_{k}}\max_{k}\frac{a_{k}}{b_{k}}, \tag{6}\]  
_where \(a_{i},b_{i}\) are the maximum spectral radii of \(A_{i},B_{i}\), respectively._  
Proof of Theorem 1.: From the \(\sin\theta\) theorem in [33], a direct conclusion is obtained as:  
\[\left\|\mathbf{D}_{k}\left(W_{c},\widehat{W}\right)\right\|=\left\|\sin \theta_{k}\left(W_{c},\widehat{W}\right)\right\|\leq\frac{\|\Sigma_{1}-\Sigma _{2}\|}{\Delta_{k}}.\]  
Considering [PERSON]'s Inequality for \(\|B_{i}\|\), we have:  
\[\left(\frac{\sum_{i=1}^{\mathrm{N}}\|\mathrm{B}_{i}\|}{\mathrm{N}}\right)^{- \frac{1}{2}}\leq\frac{1}{\mathrm{N}}\sum_{i=1}^{\mathrm{N}}\|\mathrm{B}_{i}\|^ {-\frac{1}{2}},\]  
and only if \(\|B_{1}\|=\|B_{2}\|=\cdots=\|B_{N}\|\), the equality holds. That is, \(\left(\sum_{i=1}^{\mathrm{N}}\|\mathrm{B}_{i}\|\right)^{-\frac{1}{2}}\leq \mathrm{N}^{-\frac{3}{2}}\sum_{i=1}^{\mathrm{N}}\|\mathrm{B}_{i}\|^{-\frac{1}{2}}\).