HeteroPCA Iterative Diagonal Imputation and Robust Subspace Perturbation for Heteroskedastic PCA

An iterative spectral estimation algorithm and deterministic subspace perturbation framework (introduced by Anru R. Zhang, T. Tony Cai, and Yihong Wu in 2022) for recovering the principal rank-$r$ subspace $\boldsymbol{U}$ of a low-rank signal matrix $\boldsymbol{M} = \boldsymbol{U}\boldsymbol{\Lambda}\boldsymbol{U}^\top$ from observations $\widehat{\boldsymbol{\Sigma}} = \boldsymbol{M} + \boldsymbol{Z}$ corrupted by severe diagonal heteroskedasticity $\boldsymbol{D}(\boldsymbol{Z})$. Whereas classical PCA fails when diagonal noise variances $\sigma_i^2$ are non-uniform and one-step diagonal deletion ($\boldsymbol{\Delta}(\widehat{\boldsymbol{\Sigma}})$ setting the diagonal to zero) incurs a non-vanishing rank-$r$ diagonal bias $\|\boldsymbol{D}(\boldsymbol{M})\| \asymp \frac{I(\boldsymbol{U})r}{p}\lambda_1$, HeteroPCA (Algorithm 1) initializes $\boldsymbol{N}^{(0)} = \boldsymbol{\Delta}(\widehat{\boldsymbol{\Sigma}})$ and iteratively updates $\widetilde{\boldsymbol{N}}^{(t)} = \mathrm{SVD}_r(\boldsymbol{N}^{(t)})$ (best rank-$r$ SVD approximation) followed by $\boldsymbol{N}^{(t+1)} = \boldsymbol{\Delta}(\widehat{\boldsymbol{\Sigma}}) + \boldsymbol{D}(\widetilde{\boldsymbol{N}}^{(t)})$ for $t=0,\dots,T-1$. By establishing the operator-norm contraction identities $\|\boldsymbol{D}(\boldsymbol{P}_U\boldsymbol{D}(\boldsymbol{A}))\| \le \frac{I(\boldsymbol{U})r}{p}\|\boldsymbol{D}(\boldsymbol{A})\|$ and $\|\boldsymbol{D}(\boldsymbol{P}_U\boldsymbol{A})\| \le \sqrt{\frac{I(\boldsymbol{U})r}{p}}\|\boldsymbol{A}\|$ under incoherence $I(\boldsymbol{U}) = \frac{p}{r}\max_i \|\boldsymbol{U}^\top\boldsymbol{e}_i\|_2^2$ (Lemma 1) alongside the sharp factor-2 off-diagonal operator bound $\sup_{\boldsymbol{M}\ne 0}\|\boldsymbol{\Delta}(\boldsymbol{M})\|/\|\boldsymbol{M}\| = 2 - 2/p < 2$ (Lemma 4), Theorem 3 proves the deterministic robust $\sin\Theta$ bound $\|\sin\boldsymbol{\Theta}(\widehat{\boldsymbol{U}},\boldsymbol{U})\| \lesssim \min\{\frac{\|\boldsymbol{\Delta}(\boldsymbol{Z})\|}{\sigma_r(\boldsymbol{M})}, 1\}$ completely independent of the diagonal corruption $\boldsymbol{D}(\boldsymbol{Z})$.