
New Approach to Matrix Perturbation: Beyond the Worst-Case Analysis
Van H. Vu of Yale University surveys a decade of work on matrix perturbation theory, presented as part of the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar. The talk opens with the classical foundations, Weyl's inequality for eigenvalues and the Davis-Kahan theorem for eigenvectors and eigenspaces, both known to be tight only in worst-case settings. Vu then lays out a framework that exploits the interaction between the noise matrix E and the eigenvectors of the baseline matrix A, producing sharper bounds when E is random, the typical case in applications from statistics to data analysis. Most of the hour focuses on recent results on eigenspace perturbation, with time permitting a look at extensions to other spectral functionals. The lecture assumes familiarity with linear algebra and spectral theory and is aimed at researchers in discrete mathematics and theoretical computer science rather than a general audience.