Sharp error bounds for approximate eigenvalues and singular values from subspace methods
Irina-Beatrice Haas, Yuji Nakatsukasa · 2025
Read Sharp error bounds for approximate eigenvalues and singular values from subspace methods by Irina-Beatrice Haas, Yuji Nakatsukasa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01207.txt.
Introduction
Haas and Nakatsukasa sharpen the error bars on a workhorse of numerical computing. Subspace methods pull approximate eigenvalues and singular values out of huge matrices, and the Rayleigh-Ritz step does the extracting. Their new bounds are quadratic in the residual, scaled by the gap between the value of interest and the values left behind.
Because outer eigenpairs converge fastest and carry the smallest residuals, the bounds reward exactly the cases users care about, and they stay sound even when values cluster together. The authors show the bounds are asymptotically exact, extend them to singular values of any real matrix, and test them across Krylov and randomized methods.
Catalog record
| CREATOR | Irina-Beatrice Haas, Yuji Nakatsukasa |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01207
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sharp error bounds for approximate eigenvalues and singular values from subspace methods Irina-Beatrice Haas, Yuji Nakatsukasa Abstract 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 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 x ^ i − θ i x ^ i ‖ 2 \|A\widehat{x}_{i}-\theta_{i}\widehat{x}_{i}\|_{2} , where ( θ i , x ^ i ) (\theta_{i},\widehat{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 ‖ A x ^ i − θ i x ^ i ‖ 2 2 η i c\frac{\|A\widehat{x}_{i}-\theta_{i}\widehat{x}_{i}\|_{2}^{2}}{\eta_{i}} , where η i \eta_{i} is roughly the gap between the i i th Ritz value and the eigenvalues that are not approximated by the Ritz process, and c > 1 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. 1 Introduction The symmetric eigenvalue problem and the Singular value decomposition (SVD) are key computational tasks in many numerical methods for engineering and data analysis applications. Classical algorithms perform these decompositions in polynomial time (cubic in the dimension, for an \epsilon -accurate solution), but the matrices that are considered nowadays are often of very large scale, sometimes even too large to fit into memory. Subspace methods (including Krylov subspace methods [ 20 ] and randomized algorithms [ 5 ] ) form a leading class of methods that allow us to tackle such problems. Once a subspace \mbox{Span}(Q) is identified, where Q\in\mathbb{C}^{n\times k} is a matrix with orthonormal columns, the most common approach to extracting eigenvalues is the Rayleigh-Ritz (RR) process [ 20 , Ch. 11] , which outputs the eigenvalues of Q^{*}AQ as approximations to those of A . The quality of the Ritz eigenpairs as an approximation to the actual eigenpairs of the original matrix has been extensively studied in the literature: for the eigenvectors, a bound on the canonical (or principal ) angle between the subspace spanned by the Ritz vectors and the actual eigenspace is provided in the classical Davis-Kahan sin \theta theorem [ 3 ] [ 20 , Chap.11] and was improved in [ 16 ] . For the Ritz values, error bounds have been derived in [ 12 , 7 , 20 ] [ 6 , Cor.7.3.5] [ 22 , Cor.I.4.31] . A similar process is applicable to approximate the (usually leading) singular values of A\in\mathbb{C}^{m\times n} from subspace(s) spanned by Q_{1}\in\mathbb{C}^{m\times k_{1}},Q_{2}\in\mathbb{C}^{n\times k_{2}} , as the singular values of the projected matrix Q_{1}^{*}AQ_{2} ; this is called a Petrov-Galerkin (PG) projection method. More recently, randomized algorithms such as randomized SVD by Halko, Martinson and Tropp (HMT) [ 5 ] and (Generalized) Nyström [ 17 , 2 , 24 ] have been receiving significant attention, as they provide an efficient way of computing a low-rank approximation of the original matrix that is nearly optimal in the Frobenius norm [ 5 ] . Similarly to RR and PG, randomized SVD is also based on (one-sided) projection, A\approx QQ^{T}A , where \mbox{Span}(Q)=\mbox{Span}(A\Omega) for a random (sketch) matrix \Omega . Error bounds on the resulting singular values for these methods are derived in [ 4 , 11 , 21 ] . In this paper we first examine the accuracy of the output approximate eigenvalues from the RR process. Our work is primarily motivated by the fact that existing error bounds for the Ritz eigenvalues can be improved greatly, assuming that the norms of the residuals corresponding to each eigenvalue differ significantly, which is common in practice. That is why we derive sharp upper bounds on the difference between the Ritz values and the exact eigenvalues by exploiting the perturbation structure underlying the Rayleigh-Ritz process. We then generalize the result for singular values of arbitrary matrices, and compare the bound to the approximate singular values obtained from HMT in our numerical experiments, along with other approximation methods including subspace iteration and Krylov methods. To make the problem precise, let us fix the notation and consider the structure afforded by the RR and PG processes. Notation : We use MATLAB notation for matrix indexing, in which X(:,i) denotes the i th column of X and X(:,i:j) is the matrix consisting of the i th to the j th columns of X . If not stated otherwise, we also note X_{i} the i th column of the matrix X . We let \|X\|_{2} denote the spectral norm of a matrix X , which reduces to the Euclidean norm when X is a vector. Perturbed matrix and available information from the Rayleigh-Ritz process Suppose that k eigenpairs of an n\times n symmetric matrix A are sought (typically the smallest or largest eigenpairs), and we have a k -dimensional 1 1 1 In practice one often uses a subspace whose dimension is larger than the desired number of eigenpairs k , but this does not affect what follows. trial subspace spanned by an n\times k matrix Q_{1} with orthonormal columns that approximates the corresponding eigenspace. To extract an approximation to the desired eigenpairs from Q_{1} with RR one computes the k\times k symmetric eigendecomposition Q_{1}^{\ast}AQ_{1}=Y\widehat{\Lambda}Y^{\ast} where \widehat{\Lambda}=\mbox{diag}(\theta_{1},\ldots,\theta_{k}) is the matrix of Ritz values and Y is unitary (see e.g., [ 20 , Ch. 11] ). The matrix of Ritz vectors \widehat{X}=[\widehat{x}_{1},\ldots,\widehat{x}_{k}] is defined as \widehat{X}=Q_{1}Y . Then let \widehat{X}_{\perp} be such that [\widehat{X}\ \widehat{X}_{\perp}] is a unitary matrix, and form the perturbation matrix \bar{A}=[\widehat{X}\ \widehat{X}_{\perp}]^{\ast}A[\widehat{X}\ \widehat{X}_{\perp}]=\begin{bmatrix}\widehat{\Lambda}&E^{\ast}\\ E&A_{2}\end{bmatrix} (1) where E=\widehat{X}_{\perp}^{\ast}A\widehat{X}=[E_{1},E_{2},\ldots,E_{k}] . Throughout the paper we let \lambda_{i} (resp. \sigma_{i} ) denote the i th eigenvalue (resp. singular value) of the matrix A . The overarching goal is to bound |\theta_{i}-\lambda_{i}| , the error in the Ritz values as approximations to the exact eigenvalues \lambda_{i} . In practice, the information available after RR are the Ritz pairs (\theta_{i},\widehat{x}_{i}) for i=1,\ldots,k and the norms of the columns of E , because they are equal to the norm of the residual: \|E_{i}\|_{2}=\|A\widehat{x}_{i}-\theta_{i}\widehat{x}_{i}\|_{2} . In addition, since Q_{1} is designed to approximate a k -dimensional eigenspace, a rough estimate of the eigenvalues of A_{2} is usually available. For example, when Q_{1} approximates the smallest eigenspace we can reasonably expect \lambda(A_{2})\gtrsim\max_{i}\theta_{i} (this must hold in the limit E\rightarrow 0 ), where \lambda(A_{2}) denotes the spectrum of A_{2} . Another option is to use oversampling, i.e. to approximate k+\ell eigenvalues (or singular values) so that