Unperturbed: spectral analysis beyond DavisKahan
[edit]
Proceedings of Algorithmic Learning Theory, PMLR 83:321358, 2018.
Abstract
Classical matrix perturbation results, such as Weyl’s theorem for
eigenvalues and the DavisKahan theorem for eigenvectors, are general
purpose. These classical bounds are tight in the worst case, but in many
settings suboptimal in the typical case. In this paper, we present
perturbation bounds which consider the nature of the perturbation and its
interaction with the unperturbed structure in order to obtain significant
improvements over the classical theory in many scenarios, such as when the
perturbation is random. We demonstrate the utility of these new results by
analyzing perturbations in the stochastic blockmodel where we derive much
tighter bounds than provided by the classical theory.
Related Material


