Stabilizing the Rayleigh--Ritz procedure by randomization
This solves a fundamental issue in numerical linear algebra for eigenvalue solvers, though it appears incremental as it builds on the standard Rayleigh--Ritz method.
The paper tackles the long-standing problem of extracting approximate eigenpairs with convergence rates comparable to ideal projection in eigenvalue computation, introducing a randomized Rayleigh--Ritz procedure that achieves this with similar convergence rates.
Extracting approximate eigenpairs from a prescribed subspace is of fundamental importance in eigenvalue computation. While projecting the target eigenvector onto the subspace yields satisfactory accuracy, extracting an approximate eigenpair that attains a comparable convergence rate has remained a long-standing open problem. 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. In this paper, we address this long-standing open problem by introducing a randomized Rayleigh--Ritz procedure whose output converges at a rate similar to the ideal projection. Our analysis requires only the simplicity of the target eigenvalue and extends naturally to nonlinear eigenvalue problems.