Uniform invariant subspace perturbation theory and applications

Anil Damle (Computer Science, Cornell University)

There are many classical results that allow us to understand how invariant subspaces of a matrix behave with respect to perturbations of that matrix. However, they often capture changes in invariant subspaces with respect to the spectral or Frobenius norm whereas many modern applications require control of such perturbations with respect to “row-wise” norms (such as the two-to-infinity matrix norm). For example, many algorithms for spectral clustering are either directly motivated by or may be analyzed by understanding properties of invariant subspaces.

In this talk we present new deterministic bounds on how invariant subspaces change with respect to the two-to-infinity norm as a result of perturbations to the underlying matrix. We also argue why aspects of our bounds are tight and show in what settings they improve on other recent results. In particular, understanding in what ways our bounds are tight deterministically makes them an ideal starting point for the analysis of specific algorithms and applications (particularly for random models). To illustrate this point we provide several numerical examples and show how our bounds are useful for a variety of applications.