Stabilizing the Rayleigh--Ritz procedure by randomization

Abstract

Extracting approximate eigenpairs from a prescribed subspace is of fundamental importance in eigenvalue computation. Although the standard Rayleigh--Ritz procedure is widely used for this purpose, it may suffer from deteriorated convergence of Ritz values and may even fail to produce convergent Ritz vectors, unless the compressed eigenvalue problem is assumed to be well-conditioned. In this paper, we address the eigenpair extraction problem by introducing a randomized Rayleigh--Ritz procedure. Our analysis shows that, for a simple eigenpair, the eigenvalue and eigenvector condition numbers of the randomly compressed generalized eigenvalue problem are, with high probability, comparable to those of the original problem, which yields a reliable approximate eigenpair from the extraction. The result also extends naturally to nonlinear eigenvalue problems.

arXiv commentFix some mistakes