Distributed Principal Eigenspace Estimation by Subspace Projection Averaging

A one-shot divide-and-conquer distributed principal component analysis algorithm and second-order subspace perturbation theory (introduced by Jianqing Fan, Dong Wang, Kaizheng Wang, and Ziwei Zhu in 2019). When $N = m n$ independent $d$-dimensional observations are partitioned across $m$ machines of local sample size $n$, each machine $\ell \in [m]$ computes the top-$K$ orthonormal eigenvector matrix $\widehat{\mathbf{V}}_K^{(\ell)} \in \mathcal{O}_{d \times K}$ of its local sample covariance matrix $\widehat{\boldsymbol{\Sigma}}^{(\ell)}$ and transmits $\widehat{\mathbf{V}}_K^{(\ell)}$ to a central server with $O(m K d)$ communication cost; the central server forms the averaged projection matrix $\widetilde{\boldsymbol{\Sigma}} = m^{-1}\sum_{\ell=1}^m \widehat{\mathbf{V}}_K^{(\ell)}\widehat{\mathbf{V}}_K^{(\ell)T}$ and outputs its top-$K$ eigenvectors $\widetilde{\mathbf{V}}_K \in \mathcal{O}_{d \times K}$ (Algorithm 1, Equations 3.1–3.2), which solves the least-squares subspace consensus problem $\arg\min_{\mathbf{U} \in \mathcal{O}_{d \times K}}\sum_{\ell=1}^m \rho^2(\mathbf{U}, \widehat{\mathbf{V}}_K^{(\ell)})$ where $\rho(\mathbf{U}, \mathbf{V}) = \|\mathbf{U}\mathbf{U}^T - \mathbf{V}\mathbf{V}^T\|_F$ (Lemmas 5 and 6). Using a bias–variance subspace decomposition $\rho(\widetilde{\mathbf{V}}_K, \mathbf{V}_K) \le \rho(\widetilde{\mathbf{V}}_K, \mathbf{V}_K^*) + \rho(\mathbf{V}_K^*, \mathbf{V}_K)$ where $\mathbf{V}_K^*$ is the top-$K$ eigenspace of $\boldsymbol{\Sigma}^* = \mathbb{E}[\widehat{\mathbf{V}}_K^{(\ell)}\widehat{\mathbf{V}}_K^{(\ell)T}]$ (Lemma 1), the framework proves that (1) the variance term scales as $O(\kappa\sqrt{K r / N})$ in sub-exponential $\psi_1$-norm where $r = \operatorname{Tr}(\boldsymbol{\Sigma})/\lambda_1$ is the effective rank and $\kappa = \lambda_1/\Delta$ (Theorem 1); (2) under reflection-symmetric innovation distributions $\mathbf{Z} = \boldsymbol{\Lambda}^{-1/2}\mathbf{V}^T\mathbf{X} \stackrel{d}{=} (\mathbf{I}_d - 2\mathbf{e}_j\mathbf{e}_j^T)\mathbf{Z}$ (including Gaussian and elliptical distributions), $\mathbf{V}^T\boldsymbol{\Sigma}^*\mathbf{V}$ is diagonal so the bias $\rho(\mathbf{V}_K^*, \mathbf{V}_K) = 0$ vanishes identically (Definition 4.1, Theorem 2); and (3) for general asymmetric sub-Gaussian distributions, a deterministic first-order projection expansion $\widehat{\mathbf{U}}\widehat{\mathbf{U}}^T - \mathbf{U}\mathbf{U}^T \approx f(\mathbf{E}\mathbf{U})\mathbf{U}^T + \mathbf{U}f(\mathbf{E}\mathbf{U})^T$ with quadratic residual $\le 24\sqrt{K}\varepsilon^2$ (Lemma 2) cancels the first-order zero-mean noise in expectation to yield $\rho(\mathbf{V}_K^*, \mathbf{V}_K) \lesssim \kappa^2\sqrt{K}r/n$ (Theorem 3), matching the centralized full-sample PCA rate $O(\kappa\sqrt{K r / N})$ whenever $m \lesssim n / (\kappa^2 r)$ (Theorem 4).