Spectral stability of non-normal matrices under Gaussian perturbations: Tools and applications

Mon April 10th 2023, 4:00pm
Sequoia 200
Jess Banks, UC Berkeley

An unavoidable pathology of non-normal matrices is that of spectral instability: their spectra and invariant subspaces can be highly sensitive to small perturbations. This instability can be captured by quantities such as the eigenvalue gaps, the condition number of the basis of eigenvectors, and the ϵ-pseudospectrum. In this talk we'll study the smoothed analysis of spectral (in)stability, showing that any n x n non-normal matrix, after a complex Gaussian perturbation of size δ, with high probability has eigenvalue gaps of size at least δ/poly(n), a basis of eigenvectors with condition number at most poly(n)/δ, and an ϵ-pseudospectrum with n disconnected components for all ϵ < poly(δ/n). Our focus will be on a few key tools from probability and linear algebra, as well as some important applications to algorithms for approximate matrix diagonalization.

This is joint work with Nikhil Srivastava, Archit Kulkarni, Jorge Garza-Vargas, and Satyaki Mukherjee.