The Department of Applied Mathematics weekly seminar is given by scholars and researchers working in applied mathematics, broadly interpreted.
Title: Rigorous Guarantees for Randomized Diagonalization Algorithms
Abstract: The task of designing efficient and reliable algorithms for computing the eigenvalues and eigenvectors of a matrix (i.e. solving the eigenvalue problem) is of unquestionable relevance in science and engineering. However, despite substantial progress on several of its practical facets, there are fundamental theoretical questions about the eigenvalue problem that remain poorly understood.
In this talk, I will present results that provide rigorous guarantees for two practical diagonalization algorithms. Specifically, we show that the eigenvalue problem can be solved (via the spectral bisection algorithm) in nearly matrix-multiplication time and that a certain randomized shifting strategy for the QR algorithm is globally convergent (implying an O(n^3) worst-case running time for this algorithm).
A key step in our analysis requires understanding the spectral stability properties of arbitrary deterministic matrices that have been randomly perturbed by a very small "noise matrix". With this, in the spirit of smoothed analysis, we can show rigorous guarantees for the aforementioned algorithms when run on tiny perturbations of arbitrary (possibly non-normal) inputs.
This is joint work with Jess Banks, Archit Kulkarni, and Nikhil Srivastava.