Asymmetric Low-Rank Matrix Eigenvalue and Linear-Form Eigenvector Perturbation Analysis

A non-asymptotic spectral perturbation theory (established by Yuxin Chen, Chen Cheng, and Jianqing Fan in 2021) for estimating the leading eigenvalues and eigenvectors of a low-rank symmetric matrix $\mathbf{M}^\star \in \mathbb{R}^{n\times n}$ from an asymmetrically perturbed observation $\mathbf{M} = \mathbf{M}^\star + \mathbf{H}$ whose noise entries $\{H_{ij}\}_{1\le i,j\le n}$ are mutually independent, zero-mean, and potentially heteroscedastic ($\text{Var}(H_{ij}) \le \sigma^2$, $|H_{ij}| \le B$). Using the Neumann series eigenvector expansion $\boldsymbol{u} = \frac{\lambda^\star}{\lambda}(\boldsymbol{u}^{\star\top}\boldsymbol{u})\sum_{s=0}^\infty \frac{1}{\lambda^s}\mathbf{H}^s\boldsymbol{u}^\star$ (Theorem 2) and a combinatorial graph-partition moment bound on high-order bilinear forms $|\mathbb{E}[(\boldsymbol{a}^\top\mathbf{H}^s\boldsymbol{u}^\star)^k]|$ (Lemma 5, Corollary 4), Theorem 3 establishes the master linear-form perturbation bound $|\boldsymbol{a}^\top(\boldsymbol{u} - \frac{\boldsymbol{u}^{\star\top}\boldsymbol{u}}{\lambda/\lambda^\star}\boldsymbol{u}^\star)| \lesssim \frac{\max\{\sigma\sqrt{n\log n}, B\log n\}}{|\lambda^\star|}\sqrt{\frac{\mu}{n}}$ for any deterministic unit vector $\boldsymbol{a} \in \mathbb{R}^n$. Because $\mathbb{E}[\boldsymbol{a}^\top\mathbf{H}^2\boldsymbol{u}^\star] = O(\sigma^2)$ for asymmetric independent noise versus $n\sigma^2\boldsymbol{a}^\top\boldsymbol{u}^\star$ for symmetric noise (Section 4.3), the leading eigenvalue $\lambda$ of $\mathbf{M}$ achieves $|\lambda - \lambda^\star| \lesssim \max\{\sigma\sqrt{n\log n}, B\log n\}\sqrt{\mu/n} = O(\sigma\sqrt{\mu\log n})$ (Corollary 1) — up to $O(\sqrt{n})$ times more accurate than the unadjusted leading singular value $\sigma_1(\mathbf{M})$ or the leading eigenvalue of $(\mathbf{M}+\mathbf{M}^\top)/2$, and fully adaptive to unknown heteroscedastic noise variances — while Corollaries 2–3 and Theorem 5 yield sharp linear-form and $\ell_\infty$ entrywise eigenvector bounds including for rectangular rank-1 matrices via the asymmetrized dilation matrix $\mathbf{M}_{\text{d}} = \begin{bmatrix}\mathbf{0} & \mathbf{M}_1 \\ \mathbf{M}_2^\top & \mathbf{0}\end{bmatrix}$ (Section 5.2, Equation 43).