Regional Stability and New Eigenvalue Perturbation Bounds

Abstract

Let $A$ be an $n\times n$ symmetric matrix with eigenvalues ${\lambda }_1\ge \cdots \ge {\lambda }_n$. Let $\tilde{A}:=A+E$, where $E$ is a symmetric noise matrix, and denote the eigenvalues of $\tilde{A}$ by ${\tilde{\lambda }}_1\ge \cdots \ge {\tilde{\lambda }}_n$. Bounding the perturbation $|{\tilde{\lambda }}_i-{\lambda }_i|$ is a central problem in linear algebra and numerical analysis. In this paper, we prove new perturbation results by exploring the actual interaction between $E$ and the eigenvectors of $A$. In the setting where $E$ does not act adversarially with respect to these vectors (for instance, if $E$ is random), we obtain a considerable improvement over Weyl's inequality. One can routinely extend these results to the Hermitian and rectangular settings. We obtain the new bounds as corollaries of a regional stability result, which provides a sufficient condition for a region on the real line to be stable (containing the same number of eigenvalues) after the perturbation. This result is of independent interest. We prove our regional stability result using contour integral analysis. Our main new technical ingredient here is the \textit{double-jump} argument, which is robust and could be useful in many other situations involving Neumann series.