Entrywise First-Order Eigenvector Approximation and Leave-One-Out Perturbation Analysis for Low-Expected-Rank Random Matrices

A probabilistic entrywise ($\ell_\infty$ and $2 \to \infty$ norm) eigenvector and eigenspace perturbation framework for symmetric random matrices $\mathbf{A} \in \mathbb{R}^{n \times n}$ with low-rank expectation $\mathbf{A}^* = \mathbb{E}\mathbf{A} = \mathbf{U}^*\boldsymbol{\Lambda}^*(\mathbf{U}^*)^T$ (introduced by Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong in 2020). Rather than bounding the direct entrywise difference $\|\mathbf{u}_k - \mathbf{u}_k^*\|_\infty$ via the deterministic matrix $\ell_\infty$ operator norm $\|\mathbf{A} - \mathbf{A}^*\|_\infty$, the method establishes the first-order linear entrywise approximation $\mathbf{u}_k \approx \mathbf{A}\mathbf{u}_k^* / \lambda_k^* = \mathbf{u}_k^* + (\mathbf{A} - \mathbf{A}^*)\mathbf{u}_k^* / \lambda_k^*$ and, for a general rank-$r$ principal subspace $\mathbf{U} \in \mathbb{R}^{n \times r}$ with eigengap $\Delta^*$, the polar-aligned $2 \to \infty$ approximation $\|\mathbf{U}\operatorname{sgn}(\mathbf{H}) - \mathbf{A}\mathbf{U}^*(\boldsymbol{\Lambda}^*)^{-1}\|_{2\to\infty} \lesssim (\kappa(\gamma + \varphi(1/\sqrt{n})) + \varphi(\gamma)/\bar{\gamma})\|\mathbf{U}^*\|_{2\to\infty}$ where $\operatorname{sgn}(\mathbf{H}) = \bar{\mathbf{U}}\bar{\mathbf{V}}^T$ is the matrix sign function of $\mathbf{H} = \mathbf{U}^T\mathbf{U}^*$ (Theorems 1.1 and 2.1, Corollary 2.1). The proof introduces $n$ auxiliary leave-one-out matrices $[\mathbf{A}^{(m)}]_{ij} = A_{ij}\mathbf{1}_{\{i \ne m, j \ne m\}}$ ($m=1,\dots,n$) whose leading eigenspace $\mathbf{U}^{(m)}$ is statistically independent of the $m$-th row $\mathbf{A}_{m\cdot}$ under row-and-column independence (Assumption A2), decoupling the row-concentration functional $\|(\mathbf{A} - \mathbf{A}^*)_{m\cdot}\mathbf{W}\|_2 \le \Delta^*\|\mathbf{W}\|_{2\to\infty}\varphi(\|\mathbf{W}\|_F / (\sqrt{n}\|\mathbf{W}\|_{2\to\infty}))$ (Assumption A3, Appendix A.1, Lemmas 1–5). Applied to $\mathbb{Z}_2$-synchronization, the Two-Block Stochastic Block Model $\mathrm{SBM}(n, a\log n/n, b\log n/n, J)$, and noisy matrix completion, this first-order entrywise expansion proves that unregularized spectral clustering $\widehat{\mathbf{z}} = \operatorname{sgn}(\mathbf{u}_2)$ achieves exact recovery down to the information-theoretic threshold $\sqrt{a} - \sqrt{b} > \sqrt{2}$ without trimming or cleaning, even in regimes where Theorem 3.3 proves $\sqrt{n}\|\mathbf{u}_2 - \mathbf{u}_2^*\|_\infty > 1$.