Eigenvector Under Random Perturbation: A Nonasymptotic Rayleigh-Schrödinger Theory
Provides a rigorous nonasymptotic eigenvector perturbation bound for random matrices, addressing a gap in asymptotic theory and improving upon classical results like Davis-Kahan, which is important for high-dimensional statistics and machine learning.
The paper develops a nonasymptotic Rayleigh-Schrödinger theory for eigenvectors under random perturbation, proving that with high probability, the inner product between perturbed and unperturbed eigenvectors is bounded by O(√log n / (λ₁ - λⱼ)) for all j>1 simultaneously, even when the perturbation norm exceeds the eigenvalue gap. This bound is optimal up to a log factor and improves the Davis-Kahan theorem.
Rayleigh-Schrödinger perturbation theory is a well-known theory in quantum mechanics and it offers useful characterization of eigenvectors of a perturbed matrix. Suppose $A$ and perturbation $E$ are both Hermitian matrices, $A^t = A + tE$, $\{λ_j\}_{j=1}^n$ are eigenvalues of $A$ in descending order, and $u_1, u^t_1$ are leading eigenvectors of $A$ and $A^t$. Rayleigh-Schrödinger theory shows asymptotically, $\langle u^t_1, u_j \rangle \propto t / (λ_1 - λ_j)$ where $ t = o(1)$. However, the asymptotic theory does not apply to larger $t$; in particular, it fails when $ t \| E \|_2 > λ_1 - λ_2$. In this paper, we present a nonasymptotic theory with $E$ being a random matrix. We prove that, when $t = 1$ and $E$ has independent and centered subgaussian entries above its diagonal, with high probability, \begin{equation*} | \langle u^1_1, u_j \rangle | = O(\sqrt{\log n} / (λ_1 - λ_j)), \end{equation*} for all $j>1$ simultaneously, under a condition on eigenvalues of $A$ that involves all gaps $λ_1 - λ_j$. This bound is valid, even in cases where $\| E \|_2 \gg λ_1 - λ_2$. The result is optimal, except for a log term. It also leads to an improvement of Davis-Kahan theorem.