























The eigenvalues and eigenvectors of nonnormal matrices can be unstable under perturbations of their entries. This renders an obstacle to the analysis of numerical algorithms for non-Hermitian eigenvalue problems. A recent technique to handle this issue is pseudospectral shattering [BGVKS23], showing that adding a random perturbation to any matrix has a regularizing effect on the stability of the eigenvalues and eigenvectors. Prior work has analyzed the regularizing effect of dense Gaussian perturbations, where independent noise is added to every entry of a given matrix [BVKS20, BGVKS23, BKMS21, JSS21]. We show that the same effect can be achieved by adding a sparse random perturbation. In particular, we show that given any $n\times n$ matrix $M$ of polynomially bounded norm: (a) perturbing $O(n\log^2(n))$ random entries of $M$ by adding i.i.d. complex Gaussians yields $\logκ_V(A)=O(\text{poly}\log(n))$ and $\log (1/η(A))=O(\text{poly}\log(n))$ with high probability; (b) perturbing $O(n^{1+α})$ random entries of $M$ for any constant $α>0$ yields $\logκ_V(A)=O_α(\log(n))$ and $\log(1/η(A))=O_α(\log(n))$ with high probability. Here, $κ_V(A)$ denotes the condition number of the eigenvectors of the perturbed matrix $A$ and $η(A)$ denotes its minimum eigenvalue gap. A key mechanism of the proof is to reduce the study of $κ_V(A)$ to control of the pseudospectral area and minimum eigenvalue gap of $A$, which are further reduced to estimates on the least two singular values of shifts of $A$. We obtain the required least singular value estimates via a streamlining of an argument of Tao and Vu [TV07] specialized to the case of sparse complex Gaussian perturbations. [Rest of abstract in pdf].
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。