Here is a Matlab one-liner for computing the eigenvectors of a normal matrix \(A\):

H = A+A’; S = A-A’; [U,~] = eig(randn*H+randn*1i*S);

This talk will explain why this one-liner works and what accuracy we can expect.

More generally, this talk is concerned with randomized methods for solving joint eigenvalue problems associated with a matrix family \(A_1,\ldots ,A_d\). This problem class includes the diagonalization of (nearly) commuting symmetric or nonsymmetric matrices, as well as simultaneous diagonalization by congruence. As in the Matlab one-liner above (which exploits that the Hermitian and skew-Hermitian parts of a normal matrix commute), a common idea of these randomized methods is to first reduce the matrix family to one or two matrices by random linear combinations and then apply a standard eigensolver. These methods are remarkably simple and robust, and provide a decent level of accuracy with very high probability. If needed, accuracy can be improved further with optimization techniques or other refinement strategies.

Besides algorithms, we will also discss the theory and applications of randomized solvers for joint eigenvalue problems. It turns out that classical eigenvalue perturbation theory, with a small dose of probabilistic analysis, can explain much of the success of these solvers. Applications include signal processing tasks (e.g., for image separation and EEG analysis) and tensor decomposition (e.g., for learning latent variable models). A particularly successful and important application are joint eigenvalue methods for multivariate root-finding problems, which we have explored in joint work with Bor Plestenjak.

References

• [1]  H. He and D. Kressner. Randomized joint diagonalization of symmetric matrices. SIAM J. Matrix Anal. Appl., 45(1):661–684, 2024.

• [2]  H. He and D. Kressner. A randomized algorithm for simultaneously diagonalizing symmetric matrices by congruence. arXiv:2402.16557, 2024.

• [3]  H. He and D. Kressner. A simple, randomized algorithm for diagonalizing normal matrices. arXiv:2405.18399, 2024.

• [4]  H. He, D. Kressner, and B. Plestenjak. Randomized methods for computing joint eigenvalues, with applications to multiparameter eigenvalue problems and root finding arXiv:2409.00500, 2024.