Sharp error bounds for approximate eigenvalues and singular values from subspace methods

Journal article

Subspace methods are commonly used for finding approximate eigenvalues and singular values of large-scale matrices. Once a subspace is found, the Rayleigh–Ritz method (for symmetric eigenvalue problems) and Petrov–Galerkin projection (for singular values) are the de facto method for extraction of eigenvalues and singular values. In this work we derive quadratic error bounds for approximate eigenvalues of symmetric matrices obtained via the Rayleigh–Ritz process. Our bounds take advantage of the fact that extremal eigenpairs tend to converge faster than the rest, hence having smaller residuals $\|A\hat{x}_i - \theta_i \hat{x}_i\|_2$, where $(\theta_i, \hat{x}_i)$ is a Ritz pair (approximate eigenpair). The proof uses the structure of the perturbation matrix underlying the Rayleigh–Ritz method to bound the components of its eigenvectors. In this way, we obtain a bound of the form $c\,\frac{\|A\hat{x}_i - \theta_i \hat{x}_i\|_2^{2}}{\mathrm{Gap}_i}$, where $\mathrm{Gap}_i$ is roughly the gap between the $i$th Ritz value and the eigenvalues that are not approximated by the Ritz process, and $c > 1$ is a modest scalar. Our bound is adapted to each Ritz value and is robust to clustered Ritz values, which is a key improvement over existing results. We further show that the bound is asymptotically sharp, and generalize it to singular values of arbitrary real matrices. Finally, we apply these bounds to several methods for computing eigenvalues and singular values, and illustrate the sharpness of our bounds in a number of computational settings, including Krylov methods and randomized algorithms.

Authors: Haas, I-B; Nakatsukasa, Y

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Matrix Analysis and Applications
• Volume: 47
• Issue: 1
• Pages: 308 - 329
• Publication date: 2026-02-23
• Acceptance date: 2025-10-31
• DOI: 10.1137/25m1764554
• EISSN: 1095-7162
• ISSN: 0895-4798
• Language: English
• Keywords: Petrov-Galerkin process; matrix perturbation theory; Ritz values; Rayleigh-Ritz process; singular values