Probabilistic Operator Algebra Seminar: Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time I

Seminar | January 27 | 3-4 p.m. | 748 Evans Hall

 Jorge Garza Vargas, UC Berkeley

 Department of Mathematics

In a recent joint work with J. Banks, A. Kulkarni and N. Srivastava, we have shown that on a high level, any efficient numerically stable matrix-multiplication algorithm can be turned into a diagonalization algorithm with the same properties. Quantitatively, our result significantly improves the best previously known provable running times of diagonalization algorithms. In this talk, which consists of two sessions, we will discuss the results in random matrix theory and operator theory that were used to solve this problem. In the first session we will briefly review the spectral bisection algorithm and discuss the stability of eigenvalues and eigenvectors of an arbitrary matrix. Subsequently, we will discuss the first key step towards the solution of the diagonalization problem : showing that adding Gaussian noise to any matrix leads to two desirable features for numerical diagonalization, namely increasing the matrix eigenvalue gap and improving the eigenvector condition number. In the second session we will review the notion of pseudospectrum and its relevance in this analysis. Then, we will discuss the second key step : understanding the dynamics of the pseudospectrum under Robert's Newton iteration method for computing the sign function of a matrix.